Plan Merging

About

This project is about merging single agent plans so that the result is a valid multi agent plan that is free of the following conflicts:

Edge conflicts

• Happen if two agents move along the same edge at the same time (left GIF).
• Can be resolved by doing a sidestep or taking alternative routes (right GIF) or by switching plans (middle GIF, anonymous MAPF).

Vertex conflicts

• Happen if multiple agents are at the same vertex at the same time (left GIF).
• Can be resolved by letting agents wait (right GIF) or by taking alternative routes.

An instance containing initials and single agent plans in asprilo format can be merged by using merge.py:

Usage

usage: merge.py [-h] -i INSTANCE [-r RETRIES] [-s] [-v]
  -i INSTANCE, --instance INSTANCE
                        Instance file
optional arguments:
  -h, --help            show this help message and exit
  -r RETRIES, --retries RETRIES
                        Number of retries per robot
  -s, --single          Get single agent plans and add to instance
  -v, --visualize       Visualize output with asprilo visualizer

IMPORTANT: If a seemingly easy instance doesn't get solved quickly you might want to manually try a bigger retries value with -r RETRIES. The default equals the number of agents and can in some cases lead to unsolvability or slow solving (careful: to big retrie values can have the same effect).

The solution can be obtained from the created temp.lp file. (When interrupted it is also possible to obtain a partial solution from temp.lp.)

The strategy used in this project does not guarantee optimality nor completeness.