I am looking for a pathfinding algorithm handling the following issues:

  • multiple agents

    the computed paths for agents may not lead to collisions or deadlocks in space-time

  • a stream of activities

    new pickup and delivery points for agents without assigned activities may come in at any point (usually when an agent finished their activity)

  • a very low number of branches in the underlying topology (i.e. nodes with more than two neighbors)

    I'll detail below why I am listing this.

  • inertia of agents

    some nodes are more expensive depending on from which node you came (e.g. the node you came from or one where you have to change direction)

  • size of agents

    some nodes in the vicinity of another agent may not be occupied, if they are too close

I ordered them by importance. The last two are merely nice to have, but not vital.

The paper "Lifelong Multi-Agent Path Finding for Online Pickup and Delivery Tasks." by Hang Ma, Jiaoyang Li, T. K. Satish Kumar, Sven Koenig gets really close to what I am looking for. It presents an algorithm that resolves the first two issues.

However, the algorithm struggles with, what the authors named, "not well-formed MAPD instances". In my case the following is not satisfied "for any two endpoints, there exists a path between them that traverses no other endpoints." (endpoints being starting positions of agents, pickup positions and delivery positions). Hence, why I am listing the third issue. In something similar to a PAC-MAN level there are very few possibilities to dodge other agents (compared to an open map where you can just sidestep the other agent), making conflict avoidance much harder.

The fourth issue can be resolved by modifying the underlying A*-algorithm, while the fifth issue can be baked into the conflict detection step.

Is there some literature I missed tackling this kind of issue? Or maybe how I could modify above authors' algorithm to another form of conflict resolution which works despite the problem being "not well-formed"?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.