1. Multi-agent pathfinding

Multi-agent pathfinding (MAPF) is finding collision-free paths for multiple agents.

2. Matching in MAPF

Grouping agents in MAPF into teams gives MAPFM, MAPF with matching. Agents travel to one their team's goals. An assignment from agents to goals is called a matching.

3. M*

• A complete and optimal algorithm to solve MAPF instances.
• Derived from A*.
• Plan agents independently when possible.

4. Research Questions

• How can M* be adapted to also solve MAPFM problems?
• Do existing improvements of MAPF M* also improve performance when solving MAPFM problems?
• How does M* compare to other MAPF algorithms adapted to solve MAPFM?

Two techniques were developed to add matching to M*.

5. Prematching

Agents search a path to only one of their goals at a time. All possible assignments of agents to goals are searched separately.

6. Inmatching

Inmatching searches all matchings at the same time in a single slower search process.

7. Results

Graphs display percentage solved in 2 minutes out of 200 20x20 maps, 25% filled with obstacles. Agents are split over 3 teams. All maps are guaranteed to be solvable.

8. Conclusion

• Prematching is generally preferable to Inmatching.
• Several extensions to M* and to prematching can improve the performance of M*.
• The performance of M* is comparable to that of other A* derived algorithms.

Paper

Complete explanations, results and conclusions can be found at https://mapfm-poster.donsz.nl/paper.pdf.