I'm studying AI, and we just got our final assignment.
One of the problems within it is to navigate a robot such that it picks up objects and arranges them in a given pattern, avoiding obstacles in its way. The destination point is known in advance.
This problem is not a gaming problem for me, but it certainly seems to belong in this group, since I can easily see it applying in a game situation.
I have alot of time before this is due, and I want to get it working using a good method.
Meanwhile, we have had two methods hinted at (to avoid obstacles):
a) Brute force: If you hit a wall, turn a little, and keep going. This will eventually work, but is less than inspiring. b) Find a good path, THEN follow it.
I don't want to use (a) unless I really have to, since it's very el-cheapo.
I would much rather find a good way to do (b), but I'm not sure how to go about it.
I have briefly considered 2 methods:
i) Ray casting - backwards. I'm not sure exactly how I would do this, but I was thinking to start from the destination, and try casting towards the robot. Upon failure, try to offset the angle of casting a little, until you've gone full circle (increment both +ive and -ive with each cycle). This gives me the first ray, but I then have to cast more rays (recursively) until the robot is hit. But once the initial ray finds a "way out" around the obstacles, where does the next ray begin, etc?
ii)Graph algorithms. I was thinking to define a graph of randomly (??) distributed vertices around the destination, and where there is no obstacle from one vertex to another, an edge exists. This would lend itself to a shortest-route algo. I'm VERY vague about this method, since it doesn't seem very concrete.
Anyway, my request is for hints and pointers and algorithm names.
I'm **NOT** asking for a solution, I would just like some direction, and perhaps a reference. Are my ideas worthwhile? Are they junk? etc...
I would really appreciate any response (especially via e-mail).
>One of the problems within it is to navigate a robot such that it >picks up objects and arranges them in a given pattern, avoiding >obstacles in its way. The destination point is known in advance.
>Meanwhile, we have had two methods hinted at (to avoid obstacles):
> a) Brute force: > b) Find a good path, THEN follow it.
b)
>I don't want to use (a) unless I really have to, since it's very >el-cheapo.
agreed.
>I would much rather find a good way to do (b), but I'm not sure how >to go about it.
>I have briefly considered 2 methods:
> ii)Graph algorithms. I was thinking to define a graph > of randomly (??) distributed vertices around the > destination, and where there is no obstacle from one > vertex to another, an edge exists. This would lend > itself to a shortest-route algo. I'm VERY vague about > this method, since it doesn't seem very concrete.
Then try a grid of squares (coordinate space, 2D I presume?). Easy to code, handles infinite better.
>Anyway, my request is for hints and pointers and algorithm >names.
Build a grid or a graph, depending on the coordinate space appropriate to your objects, obstacles and robot. Add obstacles to the graph/grid as they are encountered. Use a breadth-first search from the robot until the destination is encountered. Rerun it after each obstacle is added.
If you want to optimize, save the graph/grid info between obstacle encounters, instead of regenerating it. But on small grids, the search is very fast.
Avi Pilosof (a...@cse.unsw.edu.au) wrote: > One of the problems within it is to navigate a robot such that it > picks up objects and arranges them in a given pattern, avoiding > obstacles in its way. The destination point is known in advance.
You could use Potential Field as suggested by Jean-Claude Latombe ("Robot Motion Planning", ISBN 0-7923-9129-2)
Make your goal an attractive force, and obstacles to be avoided repulsive forces. Imagine a marble rolling down towards the goal. All obstacles are hills which the marble will roll around. This approach has been applied to commercial robot controllers. The disadvantage of this method is that it easily gets trapped in local minima.
> This problem is not a gaming problem for me, but it certainly > seems to belong in this group, since I can easily see it applying > in a game situation.
Indeed. I'm experimenting with the above mentioned method, and it seems to do very well for arcade type of games - very smooth motions.
I don't have the original post, but it sounds like you need a shortest path algorithm (a tried and true algorithm for doing exactly what you want). We desperately need to put this in a faq. Read the thread I started "Best Path Algorithm" if you want to know about A* and see some C++ source code.
Somebody please help out with the faq!!!! I can't. I'm writing a game and building up a nice collection of C++ code to put in the faq.
a...@cse.unsw.edu.au (Avi Pilosof) wrote: >I'm studying AI, and we just got our final assignment. >One of the problems within it is to navigate a robot such that it >picks up objects and arranges them in a given pattern, avoiding >obstacles in its way. The destination point is known in advance. >This problem is not a gaming problem for me, but it certainly >seems to belong in this group, since I can easily see it applying >in a game situation.
Try some shortest path algorithms. Take a look at my web page for some solutions, including a description of the A* algorithm.
: You could use Potential Field as suggested by Jean-Claude Latombe : ("Robot Motion Planning", ISBN 0-7923-9129-2)
: Make your goal an attractive force, and obstacles to be avoided : repulsive forces. Imagine a marble rolling down towards the goal. : All obstacles are hills which the marble will roll around. This : approach has been applied to commercial robot controllers. The : disadvantage of this method is that it easily gets trapped in : local minima.
This sounds like what one uses in flocking algorithms: At each "frame", the destination contributes a vector, and the obstacle(s) contributes a vector.
However, as you say, I'm not guaranteed to reach my destination. If there's an obstacle lying between me and my target, such that it is perpendicular to the line created between me and my target, I will eventually come to a stop as the forces balance...
: Make your goal an attractive force, and obstacles to be avoided : repulsive forces. Imagine a marble rolling down towards the goal. : All obstacles are hills which the marble will roll around. This : approach has been applied to commercial robot controllers. The : disadvantage of this method is that it easily gets trapped in : local minima.
Aces of the Deep used this very same method for handling their destroyer/convoy/submarine AI. It works like a charm.
Steve +========================================================================== ===+ | _ | | Steven Woodcock _____C .._. | | Senior Software Engineer, Gameware ____/ \___/ | | Lockheed Martin Information Systems Group <____/\_---\_\ "Ferretman" | | Phone: 719-597-5413 | | E-mail: woodc...@escmail.orl.mmc.com (Work), swood...@cris.com (Home) | | Web: http://www.cris.com/~swoodcoc/wyrdhaven.html (Top level page) | | http://www.cris.com/~swoodcoc/ai.html (Game AI page) | | Disclaimer: My opinions in NO way reflect the opinions of | | the Lockheed Martin Information Systems Group | +========================================================================== ===+
:>: The disadvantage of this method is that it easily gets trapped in :>: local minima.
I found, in my implementation using the above technique, it was very easy to trap an AI player, such as...
T
XXXXX X X X X X
A
Using a slightly modified A* search, the AI player would end up in the U, trapped for all intents and purposes. Anyone have any ideas on this, as I really don't want to redo this approach, as the rest of it works well! :)
D.Mills
______________________________________________________________ Dean Mills - Savage SoftWare Company Team OS/2 Member
E-Mail - dmi...@mi.net - dataw...@ftcnet.com Savage SoftWare, a division of Savage Online Services Inc. ______________________________________________________________
In article <4k9k6v$...@scratchy.mi.net>, Dean Mills <dmi...@mi.net> wrote: >:>: The disadvantage of this method is that it easily gets trapped in >:>: local minima.
>I found, in my implementation using the above technique, it was very easy to >trap an AI player, such as...
> T
> XXXXX > X X > X X > X
> A
>Using a slightly modified A* search, the AI player would end up in the U, >trapped for all intents and purposes. Anyone have any ideas on this, as I >really don't want to redo this approach, as the rest of it works well! :)
>D.Mills
>______________________________________________________________ > Dean Mills - Savage SoftWare Company > Team OS/2 Member
> E-Mail - dmi...@mi.net - dataw...@ftcnet.com > Savage SoftWare, a division of Savage Online Services Inc. >______________________________________________________________
Just modify your maps so that all blocking terrain is convex. ;-) Seriously though, I'm guessing that this situation while comman and stiffling, isn't the usual one, and that this kind of "springy" AI normally works fairly well.
If this is the case, couldn't you just put in a special case if the AI get stuck? So if your AI can't go where it wants, you can switch to some other AI for a while. The problem naturally is when to switch back to the springy AI, but I'd guess you could start with something simple like returning as soon as you had direct line of sight.
Another option might be to combine this with some sort of pre computed "best path routes" between general areas, and let that kick in if you really got stuck.
In article <4k9k6v$...@scratchy.mi.net>, dmi...@mi.net (Dean Mills) wrote: >:>: The disadvantage of this method is that it easily gets trapped in >:>: local minima.
>I found, in my implementation using the above technique, it was very easy to >trap an AI player, such as...
> T
> XXXXX > X X > X X > X
> A
>Using a slightly modified A* search, the AI player would end up in the U, >trapped for all intents and purposes. Anyone have any ideas on this, as I >really don't want to redo this approach, as the rest of it works well! :)
If you have a way of determining when the AI player is trapped (can't find novel movements, consumes too much time, ...), then you could switch the AI governing the computer player. For example, in the situation presented above, the AI/strategy of always turning left or always turning right would easily solve the problem.
Now that I think about it, it seems as though I am suggesting that you implement a superAI, in the sense that this AI would select the most appropriate AI to use when faced with a certain environment. In the current scenario, the superAI would utilise your AI until the computer player is trapped. When this situation arises, the superAI would now utilise the TurnLeft/TurnRight AI until either the destination is reached or the computer player is once again moving in the direction of the goal.
In article <4k9k6v$...@scratchy.mi.net>, From dmi...@mi.net (Dean Mills), the following was written:
> Using a slightly modified A* search, the AI player would end up in the > U, trapped for all intents and purposes. Anyone have any ideas on > this, as
Simple. Remove the 'U' from the map.
Instead of exerting more effort in making the movement algorithm smarter you just make the map simpler.
In <4k9k6v$...@scratchy.mi.net> dmi...@mi.net (Dean Mills) writes:
>:>: The disadvantage of this method is that it easily gets trapped in >:>: local minima. >I found, in my implementation using the above technique, it was very easy to >trap an AI player, such as... > T > XXXXX > X X > X X > X > A >Using a slightly modified A* search, the AI player would end up in the U, >trapped for all intents and purposes. Anyone have any ideas on this, as I >really don't want to redo this approach, as the rest of it works well! :)
How about using a hierarchical method for determining the path? Organize the terrain into something similar to a quad tree. Take your pick how you construct it. The weighting of each "quad" is the average of all those within. (Storing min and max might be useful as well...)
Now this is how the algorithm would work. At the highest level of granularity pick the path to your destination which requires the least amount of "effort". Now enter the first "quad" that is on the path. Bump down to the next level of granularity, recursively applying the same algorithm. The trick here is, if you encounter a position where you can't go anywhere, bump back up to the previous level of granularity and select a path which requires a little more effort.
Such an algorithm, or one similar to it, would at the very least allow you to "back out" of corners like the one you described above. Add a little bit of lookahead before moving and you're set.
> :>: The disadvantage of this method is that it easily gets trapped in > :>: local minima.
> I found, in my implementation using the above technique, it was very easy to > trap an AI player, such as...
You basicly have two options. Either avoid the local minima, or escape it trapped.
The former is the preferred option, but it can be somewhat tricky. One possibility is to use "beacons" -- well-placed attractive points. Let the object travel from one beacon to the next until its destination is within sight.
If you choose the latter option, you could try something like this:
1) Detect a dead-end (if the object doesn't reach its destination within a specified time, or if it stays too long in a small area) 2) Pick a random location which is reachable from the current location, and go there first. 3) When you reach the random location, go to the desired location.
There are plenty of other methods for both options though.
Steve Hodsdon <103365....@compuserve.com> spake thusly:
>Simple. Remove the 'U' from the map.
>Instead of exerting more effort in making the movement algorithm smarter >you just make the map simpler.
You cannot do this if writing an AI for a game like Bolo. Players just olug in AI brains and use their own maps. You have no control (nor should you, really).
That said, at one time I gave a lot of thought to various movement algorithms. I came up with one whose one requirement is that LOS must be cheap to calculate. I'll post it if anyone's interested.
-- Robert Uhl | Save the Ales! Homebrewer Since 1995 Orthodox Christian | If you like the Macintosh, send mail to Macintosh Programmer | evangel...@macway.com for information about the Bolo Player (Spectre) | EvangeList, Guy Kawasaki's list for Mac advocates.
> In article <4k9k6v$...@scratchy.mi.net>, Dean Mills <dmi...@mi.net> wrote: > >Using a slightly modified A* search, the AI player would end up in the U, > >trapped for all intents and purposes. Anyone have any ideas on this, as I > >really don't want to redo this approach, as the rest of it works well! :) > Just modify your maps so that all blocking terrain is convex. ;-)
Chris Crawford once spent a long time on just this exact problem...and finally realized that the best solution was removing concave areas from the map. A* should fix this problem, so that slight modification must be breaking it.
> Seriously though, I'm guessing that this situation while comman and > stiffling, isn't the usual one, and that this kind of "springy" AI > normally works fairly well.
> If this is the case, couldn't you just put in a special case if the AI > get stuck? So if your AI can't go where it wants, you can switch to some > other AI for a while. The problem naturally is when to switch back to > the springy AI, but I'd guess you could start with something simple like > returning as soon as you had direct line of sight.
Yup. If your attractor/repulsor AI is breaking A*, just detect for stuck or "dancing" units and drop back to a real A* or Djykstra's (sp?) for a few turns.
> Another option might be to combine this with some sort of pre computed > "best path routes" between general areas, and let that kick in if you really > got stuck.
This adds an extra benefit to the AI...pre-planned tactics ala pincer moves etc.
I would use attractor/repulsor to determine targets, then use Djykstra's to compute a true shortest path that avoids heavy repulsor (defended) areas and follow that path. If the target is moving, you can re-evaluate or choose to follow the attack path for a few turns anyway...
In article <4kdh4f$...@dub-news-svc-5.compuserve.com>,
Steve Hodsdon <103365....@compuserve.com> wrote: >In article <4k9k6v$...@scratchy.mi.net>, From dmi...@mi.net (Dean >Mills), the following was written: >> Using a slightly modified A* search, the AI player would end up in the
>> U, trapped for all intents and purposes. Anyone have any ideas on >> this, as
>Simple. Remove the 'U' from the map.
>Instead of exerting more effort in making the movement algorithm smarter >you just make the map simpler.
>Steve
Better yet, just remove all terrain... This should do wonders in simplifying your AI. ;-)
Robert A. Uhl (r...@odin.cair.du.edu) opined thusly: : You cannot do this if writing an AI for a game like Bolo. Players : just olug in AI brains and use their own maps. You have no control : (nor should you, really).
Well said Robert!
: That said, at one time I gave a lot of thought to various movement : algorithms. I came up with one whose one requirement is that LOS must : be cheap to calculate. I'll post it if anyone's interested.
Hey, I'd like to see it. I'm always looking for fast code that I won't have to write myself...... ;)
Steven Woodcock "The One and Only"
+========================================================================== ===+ | _ | | Steven Woodcock _____C .._. | | Senior Software Engineer, Gameware ____/ \___/ | | Lockheed Martin Information Systems Group <____/\_---\_\ "Ferretman" | | Phone: 719-597-5413 | | E-mail: woodc...@escmail.orl.mmc.com (Work), swood...@cris.com (Home) | | Web: http://www.cris.com/~swoodcoc/wyrdhaven.html (Top level page) | | http://www.cris.com/~swoodcoc/ai.html (Game AI page) | | Disclaimer: My opinions in NO way reflect the opinions of | | the Lockheed Martin Information Systems Group | +========================================================================== ===+
>> :>: The disadvantage of this method is that it easily gets trapped in >> :>: local minima.
>> I found, in my implementation using the above technique, it was very easy to >> trap an AI player, such as...
>You basicly have two options. Either avoid the local minima, or escape >it trapped.
>The former is the preferred option, but it can be somewhat tricky. >One possibility is to use "beacons" -- well-placed attractive >points. Let the object travel from one beacon to the next until its >destination is within sight.
The main problem with this is that you have to setup beacons for all maps by hand... Although most games have premade terrain anyway. You could also just make concave areas more powerfull repulsors than other blocking terrain. Ideally the same terrain could be attractive or repulsive in different strengths for different types of units (e.g. ground as opposed to naval).
I'm wondering how effective writing code to try to figure out how to place attractors and repulsors would be... Any ideas?
To: PhilljasUnknownx.engr.orst.edu Subject: Re: Avoiding Obstacles to
Ph> Just modify your maps so that all blocking terrain is convex. ;-)
Seriously, that is a viable solution.
Ph> If this is the case, couldn't you just put in a special case if the AI Ph> get stuck? So if your AI can't go where it wants, you can switch to
Question: How does it tell when it is stuck?
Ph> Another option might be to combine this with some sort of pre computed Ph> "best path routes" between general areas, and let that kick in if you Ph> really got stuck.
: To: PhilljasUnknownx.engr.orst.edu : Subject: Re: Avoiding Obstacles to
: Ph> Just modify your maps so that all blocking terrain is convex. ;-)
: Seriously, that is a viable solution.
: Ph> If this is the case, couldn't you just put in a special case if the AI : Ph> get stuck? So if your AI can't go where it wants, you can switch to
: Question: How does it tell when it is stuck?
Alternatively, why not just define your terrain as not having obstacles your units can *never* cross? Replace those with "expensive" terrain that take long to cross, but not impossible, and your convex/concave problem goes away as well.
: Ph> Another option might be to combine this with some sort of pre computed : Ph> "best path routes" between general areas, and let that kick in if you : Ph> really got stuck.
: It'd get stuck because of those too if the map is modifiable.
How's WASTED coming along, Sunir? :) Oh, I'm sorry, was it WASTE instead? :)
dmi...@mi.net (Dean Mills) wrote: > :>: The disadvantage of this method is that it easily gets trapped in > :>: local minima.
> I found, in my implementation using the above technique, it was very easy to > trap an AI player, such as...
> T
> XXXXX > X X > X X > X
> A
When the piece gets trapped, take a note of the cells occupied by the obstacle. Follow the left-hand wall until no part of the obstacle lies between the piece and the target, then continue. [Simple algorithm.]
If you've got the processing power and storage space free then precompute the path before you start out on any journey. [Extra marks.]
Point to ponder: what governs whether you should follow the left-hand or right-hand wall ? [You can take a *good* guess from the 'Simple' alg.]
Simon. -- slav...@hearsay.demon.co.uk -- the poster | "Sometimes a .sig is just formerly known as slav...@entergrp.demon.co.uk. | a .sig." -- Sigmund Freud.
Avi Pilosof <a...@cse.unsw.edu.au> wrote: >I'm studying AI, and we just got our final assignment.
>One of the problems within it is to navigate a robot such that it >picks up objects and arranges them in a given pattern, avoiding >obstacles in its way. The destination point is known in advance.
[...]
>I have alot of time before this is due, and I want to get it working >using a good method.
>Meanwhile, we have had two methods hinted at (to avoid obstacles):
> a) Brute force: If you hit a wall, turn a little, and keep > going. This will eventually work, but is less than > inspiring. > b) Find a good path, THEN follow it.
>I don't want to use (a) unless I really have to, since it's very >el-cheapo.
>I would much rather find a good way to do (b), but I'm not sure how >to go about it.
[...] >I'm **NOT** asking for a solution, I would just like some direction, >and perhaps a reference. Are my ideas worthwhile? Are they junk? etc...
>I would really appreciate any response (especially via e-mail).
As someone already mentioned, a quad-tree. Take a big square. If it is completely free, mark it as clear. If it is completely blocked, mark it as blocked. If it is partially clear, give this square 4 children (in effect dividing it into 2x2) and repeat this procedure for all of the children.
At the end of this, you'll have a number of squares in this tree-structure, all the leaves will be either impassable or clear.
Search recursively for a path from free square to free square.
Once you have such a path, proceed from the center of each free square to the next.
This should be pretty fast. It will work especially well for a large board that is mostly free space. Since you are stepping from the center of one square to another, you will have a slightly jagged looking path. Once you have the quad-tree in place it will work for going from anywhere to anywhere.
Here's another idea, rather like a breadth-first search but using the board itself to store things. It's a modified flood-fill.
-- WARNING -- THE FOLLOWING MAY BE CONSIDERED A 'SOLUTION'
I call it "Ant Races".
Have a list of ants, starting out at the start. Each ant knows how many moves it took to get where it is. Each turn, each ant moves into a free space and 'colors' that space with the current number of ticks elapsed. If there is more than 1 free space the ant can get to, it spawns a child (to be added to the list of ants) for each extra free space. Ants that cannot get to a free space will die and be removed from the list of ants.
Start with one ant at your destination.
Once you arrive at the start, you can trace your path back by always going down the gradient.
This should be much faster than the typical breadth-first search, because you don't have to check an open or a closed list -- just look at the board. The algorithm is O(size of board) -- every square on the board is looked at some constant factor of times, maybe 2.5 times or so.
It's simple to implement and will give you a very close to optimal path. The drawback is that you have to repeat all that work for every different start/destination, so it isn't the best if you have to do a bunch of paths from/to different places. For that, I would suggest the quad-tree.
Jasper Phillips wrote: > The main problem with this is that you have to setup beacons for all maps > by hand... Although most games have premade terrain anyway. You could also > just make concave areas more powerfull repulsors than other blocking terrain.
This could be a problem if your target is within the concavity at some stage.
> I'm wondering how effective writing code to try to figure out how to place > attractors and repulsors would be... Any ideas?
I think selecting the "beacons" from the meeting points (vertices) of a Voronoi diagram could be pretty effective.
NB: I've quoted the word "beacons" because it usually has a slightly different meaning in robotics.
ss...@intranet.ca wrote: > Question: How does it tell when it is stuck?
The easy way out would be to use time. The object could be considered stuck either if it hasn't reached its destination within a reasonable time, or if it stays in the same area for too long.
|
