Hi... First of all, i would like to say that i have never worked on AI algorithms before. This is my first time on such subject and i don't know how much AI can help. Here is the problem. I have a lattice with arbitrary dimensions (in 2D or 3D), and i want to fill it with chains. A chain can be of arbitrary length, and it is composed of small spheres. Each sphere has exactly the dimensions required to fill a single cell. The way each chain can grow is random. It can start from a randomly selected, empty cell, and it can grow to any random direction. Directions are : UP, DOWN, LEFT and RIGHT (no diagonal movement). Its length is random, in the sense that all the chains in the lattice must follow a Poisson distribution (distribution around a predefined average chain length). The goal is to fill the lattice with chains, until the free volume (in 3D, or free area in 2D) reaches a predefined minimum (about 10%). The key to all this, is that the chains can't share cells in the lattice. In other words, every cell must hold only one sphere. The rules for the whole process are : a) chains' length must follow a Poisson distribution (without gaps), b) the free volume must be equal to the predefined free volume (with a 2% error) c) no cell sharing between chains. I know that for this kind of problems, brute force algorithms are the best candidates. And, because of this, i tried to develop such an algorithm. The problem is that in case to follow all the rules, the best free volume i can achieve is 22.5% in almost any lattice size. And this is not enough. So i thought that some kind of pathfinding, for inserting chains that can't be inserted (totally) randomly, can be used. E.g. when my algo tries to insert a chain in the lattice, and after 5000 trials with different (random) start positions, i could use some kind of pathfinding in case to "drive" chain inside the lattice without violating the above 3 rules. I would like to know if there is such an algorithm, and if there is, where can i find info on it? Something like A* (A star) without knowing the target position, but knowing the number of steps we can do (number of spheres). Thanks in advance. HellRaiZer PS. Another reason for using somekind of AI algorithm, is to be able to know (early in the execution) if i can insert a chain with a predefined length in the lattice. This means, to be able to know if by trying to insert the chain one more time, will do any good to the whole process.

Um, what are you allowed to actually decide? The way you just described the problem, you said the starting positions, the lengths, the directions are all random. What parts of this thing can we actually control?

Maybe restating the problem to make it clear what we're working with would help. Can we choose where to start placing a chain? What directions it goes in? Are the chains generated in advance, or do we only get to see the next chain after we've placed the previous one?

If we completely control the positions of the chains, we can just weave back and forth filling up the space systematically, but somehow I don't think this is what you want.

Probably genetic algorithms, if you never have experience with these look at and play with that program and documentation. Of course you'd need to write your own fitting function, and the algorithms would be slightly different. He tried to find suboptimal solution for traveller problem for 1000 - 10000 points

BTW did you mean by random :defined by purely random function, or :it's an arbitrary decision?

If you ment you can choose starting position of chain and a rotation parallel to an axis, then its a simillar problem to the bin packing problem. If it's just a variation for bin packing problem there is very little reason why to do it by AI. There are quite simple and somewhat effective algorithm for aproximation that uses something as simple as sorting.

Thanks for the quick reply!

AP:
I'll try to make things a little more clear.

Quote:
Um, what are you allowed to actually decide? The way you just described the problem, you said the starting positions, the lengths, the directions are all random. What parts of this thing can we actually control?

First of all, we can't control lengths. What we have is the average chain length, and a function that generates random deviates based on Poisson distribution. In other words, length is random, but not totally random. For example, if we set the average chain length to 30, we can calculate from the beginning (an approximation of) the percentage of the chains that will have certain lengths based on the distribution. BUT, what we have is a percentage. What we don't have is the actual total number of chains in the lattice. So, in case to get a first approximation, i keep calculating chain lengths until the free volume get below the predefined threshold. If the number of chains is big enough we can guarantee a (approximation of) a Poisson distribution. I hope this makes sense. We can't control the lengths.

Quote:
Can we choose where to start placing a chain? What directions it goes in?

In a few words, the whole thing must look random (even if it's not). What i mean is that, things like inserting all the chains horizontally or vertically, or any other "not-random" order doesn't work! Or in other words, the resulted free volume must be randomly placed inside the lattice.
Directions must be random (or at least look random).
Starting positons can be random but it is not crucial. It was my desicion to place the chains in random positions. This made the free volume more random.

Quote:
Are the chains generated in advance, or do we only get to see the next chain after we've placed the previous one?

No, you can do it in what ever way you want, but keep in mind the rules!
In my implementation, i decided to place the chains one by one, because that seemed easier. But generating the chains in parallel is a thought. Also growing the chain from both its ends is also a option.

Quote:
If we completely control the positions of the chains, we can just weave back and forth filling up the space systematically, but somehow I don't think this is what you want.

As i said, this doesn't work. The resulted lattice will be used later for other things, and those things need a random lattice.

Now i understand that the explanation i gave in the first post wasn't clear enough. When i mentioned pathfinding or any other AI algorithm, i didn't meant "for using it in the whole process". Let me explain (the numbers are not completely correct!).

Data-------------------Lattice : 512 x 512Average Chain Length : 30Target Free Volume : 10%

These give us about 8000 chains. From them about 60% will have lengths in range [23, 37].
When we start placing chains in the lattice we can place them wherever we want. But from some point and after we will have to try and find a good place to insert the chains. I was thinking if it was possible, when we have inserted, say 80% of the chains randomly, to force the remaining chains to be inserted, by "driving" them inside the lattice. If the directions and starting positions of the first 80% was random, then by inserting the rest systematically, will still result in a random lattice.

I hope it is more clear. If you have more questions, please ask.

Raghar:
I think you forgot a link :)

Quote:
BTW did you mean by random :defined by purely random function, or :it's an arbitrary decision?

As i said, directions must be totally random.

Quote:
If you ment you can choose starting position of chain and a rotation parallel to an axis, then its a simillar problem to the bin packing problem. If it's just a variation for bin packing problem there is very little reason why to do it by AI. There are quite simple and somewhat effective algorithm for aproximation that uses something as simple as sorting.

I don't completely understand what you mean. I don't know what is the bin packing problem, so i can't tell if it is like it. I'll try to find more info on this.

Thanks.

HellRaiZer

Based on your description, the chains just have to "look" random within the lattice, right? So we can actually generate chains in the lattice by random and "grow" them "around" pre-existing chains and they will still look random, correct?

This problem may be much harder than you think.....I think the general complexity of it is very high....

First of all, I think you need to construct a mathematical model of it. Because there might be thresholds for open space that are unreachable. If the lengths are random, and 60% are between 23 and 37 link, then I would imagine that there is a certain probability that you can accidentally subdivide the space into isolated subregions of less than 23 - 37 free spaces. This will become your worst case scenario. So, say you have a large 2D lattice, then there is the chance that you will accidentally subdivide the entire lattice into say empty regions of about 20 free spaces. If that happens, you may have like less than a 30% chance of actually generating a chain that will fit in the region, no to mention the chain has to fit in shape-wise.

Basically, you need to factor in these probabilities before actually setting a threshold for empty spaces. You will most likely see a phase transition in problem toughness. There will very well be a threshold beyond which there is no way of solving the problem probabilistically. So, keep that in mind and go back to look at your threshold settings again, since its futile to try and solve an unsolvable problem with something that is only good at giving pretty good solutions and not the best solution (sometimes) like many AI methods.

As for possible routes of attack, try looking into Ant Systems and Ant Colony Optimization. You may be able to map those algorithms into a different form on your problem by using the pheromone concept and solution construction. Or there are other iterative improvement methods, which you might look into.

Take a look at Constraint Satisfaction Problems (CSPs). You could even incorporate portions of your stochastic models into these. These techniques when properly applied allow problems such as "n Queens" or filling a crossword puzzle with all possibilities from a dictionary possible in very short amounts of time (compared with brute force). They are also used for problems such as VLSI design where you must place elements on a chip to minimize area.

If you can formalize the list of constraints which you presented above, then you can likely adapt the CSP methods to your problems. They are also discussed in many graduate-level intro to AI books (see for instance AI: A Modern Approach by Russel).

WeirdoFu:

Quote:
Based on your description, the chains just have to "look" random within the lattice, right? So we can actually generate chains in the lattice by random and "grow" them "around" pre-existing chains and they will still look random, correct?

Yes that's correct.

Quote:
So, keep that in mind and go back to look at your threshold settings again, since its futile to try and solve an unsolvable problem with something that is only good at giving pretty good solutions and not the best solution (sometimes) like many AI methods.

You have a point here! Satysfing all three rules simultaneously makes the problem very hard to solve for the reasons you described (empty space distribution). In my current implementation, I try to get the free volume as close as possible to the predefined threshold, without violating the other two rules (chain length and cell sharing). I have also tried to an alternative where the free volume is a hard constraint (can't be violated), but i can play with the chain distribution (by not inserting chains with lengths that can't be inserted). That introduce gaps in the distribution (e.g. no chain with 23 spheres will be inserted in the lattice).

Quote:
As for possible routes of attack, try looking into Ant Systems and Ant Colony Optimization.

I'll look into these. Thanks.

mnansgar:
Thanks for the info. I'll see what i can get from this.

Btw, you mentioned VLSI design. The whole thing is about something in the same area (microelectronics). It's about dissolution of thin polymer films for use in lithography simulation (lattice = film, chains = polymer chains, spheres = monomers).

Thanks for the replies.

HellRaiZer