A* is a search algorithm that uses a heuristic function to prioritize promising places to search. In MAPF, there are several heuristics possible, such as
- Sum of Manhattan distances from all agents to their goals
- Sum of shortest path distance from all agents to their goals
Every state (combination of agent positions) corresponds to a node in A* Every node has its own cost (what it costs to reach the node) and heuristic (estimated cost to the goal) The node with the lowest cost+heuristic is evaluated first. This can be done using a priority queue.
Several child nodes can be created by applying operators.
For example, for one agent, an operator could be move to the right
.
For multiple agents, it is the cartesian product of all operators of the individual agents.
Partial Expansion A* improves the memory efficiency of A* by reducing the queue size.
This is done by collapsing less promising nodes, i.e. with a low cost+heuristic
, into their parent node.
Thanks to Ivar de Bruin for helping with ID and A*: