MAPF Problem Instance Generator Integration#

LSMART Pipeline

The instance generator is responsible for generating the next MAPF problem instance by:

  1. computing a commit cut on the ADG to determine the start states of the AGVs,

  2. assigning goals to the AGVs,

  3. refining the goals to satisfy planner-specific assumptions if necessary.

To compute the commit cut, we use the same algorithm from Hönig et al. 2019, which looks into the future for \(\frac{T}{\epsilon}\) actions for each AGV, where \(T\) is the planner time limit and \(\epsilon\) is the minimal amount of time for an AGV to finish one action. Since LSMART focuses on evaluating MAPF algorithms, we use a random goal assigner.

Our Provided Instance Generators#

We provide three instance generators, including:

  • windowed: the windowed task assigner (Li et al. 2021), which assigns tasks within the planning window. This can only be used with the RHCR planner.

  • distinct-one-goal: the distinct one-goal task assigner, which assigns each robot a distinct goal. This can only be used with the PBS and MASS planners.

  • one-goal: the one-goal task assigner, which assigns each robot a goal regardless of duplicates. This can only be used with the TPBS planner.

Add New Instance Generators#

Implementing a new instance generator requires no RPC communication since it is handled within LSMART. The instance generator shall inherit the abstract class Class BasicTaskAssigner and implement the pure virtual functions defined in the class. As an example, we refer the users to Class WindowedTaskAssigner for the windowed instance generator.

class BasicTaskAssigner#

An abstract class for task assigners.

This class provides the interface for task assigners. It contains methods for updating start and goal locations, loading tasks from a file, and getting the current start and goal locations. It also provides methods for sampling locations from the map.

Subclassed by DistinctOneGoalTaskAssigner, OneGoalTaskAssigner, WindowedTaskAssigner

Public Functions

BasicTaskAssigner(const SMARTGrid &G, const shared_ptr<HeuristicTableBase> heuristic_table, int screen, int num_of_agents, int seed, string task_file = "")#

Constructor for BasicTaskAssigner.

Parameters:

  • G – The SMARTGrid representing the map.

  • heuristic_table – A shared pointer to the heuristic table.

  • screen – The screen number for logging.

  • num_of_agents – The number of robots.

  • seed – The random seed.

  • task_file – The file containing the tasks. If empty, tasks are randomly generated.

virtual void updateStartsAndGoals(vector<tuple<double, double, int>> &start_locs, set<int> finished_tasks_id) = 0#

Virtual function to update start and goal locations.

Parameters:

  • start_locs – A vector of tuples representing the start locations.

  • finished_tasks_id – A set of finished task IDs.