Multi-agent pathfinding

[Dave]

Archived from groups: comp.ai.games (More info?)

Hi,

I'm looking for information on multi-agent pathfinding, either from
academic research or the games industry.

The problem: find optimal or near-optimal routes on a grid to get n
agents to n different destinations, avoiding collisions.

I'm looking at ways to improve on the usual approach (A* for each
agent, and then recompute route every time a collision is imminent)

Thanks!
Dave

 

[Guest]

Archived from groups: comp.ai.games (More info?)

Dave wrote:

> Hi,
>
> I'm looking for information on multi-agent pathfinding, either from
> academic research or the games industry.
>
> The problem: find optimal or near-optimal routes on a grid to get n
> agents to n different destinations, avoiding collisions.
>
> I'm looking at ways to improve on the usual approach (A* for each
> agent, and then recompute route every time a collision is imminent)
>
> Thanks!
> Dave
Automated planning may be of interest to you.

--
Surendra Singhi

www.public.asu.edu/~sksinghi

 

[marc]

Archived from groups: comp.ai.games (More info?)

Dave wrote:

> I'm looking for information on multi-agent pathfinding, either from
> academic research or the games industry.
> The problem: find optimal or near-optimal routes on a grid to get n
> agents to n different destinations, avoiding collisions.
> I'm looking at ways to improve on the usual approach (A* for each
> agent, and then recompute route every time a collision is imminent)

Not sure thats the usual approach. For my stuff[1] I do an A* path
plan every so often on each agent. This makes sure and catches doors
closing and such.
However, this A* stuff doesnt take into account any other agents,
just large moving objects that affect nav.
For more mobile objects I use avoidance code that works on a local
level.


[1] did all the Nav work for Oddworld: Stranger's Wrath, out soon.

--
marc

 

[Guest]

Archived from groups: comp.ai.games (More info?)

On Thu, 25 Nov 2004 12:07:26 -0800, Dave wrote:

> The problem: find optimal or near-optimal routes on a grid to get n
> agents to n different destinations, avoiding collisions.
>
> I'm looking at ways to improve on the usual approach (A* for each
> agent, and then recompute route every time a collision is imminent)

The references found at the following URL may help you:

http://groups.google.dk/groups?selm=3BBECC0A.D1798EE4%40mail1.stofanet.dk

--
mail1dotstofanetdotdk