hog2 - MAPF extensions

HOG2 is a package containing combinatorial search algorithms forked from Nathan Sturtevant's repository

This fork extends HOG2 with multi-agent pathfinding algorithms

Multi-Agent Pathfinding (MAPF) Definition

The muli-agent planning problem is defined as a set of k agents A={a₁,…,a_k}, a graph G=(V,E) of the state space where V is set of all possible states that an agent may take, for example, a state could be latitude/longitude coordinates, or x,y,z location, etc. E is the set of edges between states representing actions that each agent may take to transition between states. Each agent has an initial state {s₁,…,s_k} and a goal state {g₁,…,g_k}. The objective is to find a set of paths P={p₁,…,p_k} for each agent from it’s start to it’s goal. Each path p_i is a sequence of states such that p_i[0]=s_i and p_i[end]=g_i and all states in each p_i are adjacent, meaning they are connected by an edge in E.

In addition, we require that there are no conflicts in P. That is, no pair of path points p_i[n],p_j[m] may occupy the same state at the same time. (In other words the agents cannot collide into each other.) We also seek solutions which are optimal, meaning each p_i is as short as possible -- it minimizes the distance (or time or fuel, etc.) required to maneuver from start to goal. Optimality can be measured with respect to makespan (minimization of the largest cost to completion for all agents), or flowspan (sum of costs for all agents). The algorithms herein are targeted toward flowspan but are usable for makespan with minimal changes.

Dependencies

C++11 or newer

Google Test

OpenGL (optional -- code can be compiled with OpenGL turned off using OPENGL=STUB)

Building

cd build/gmake && make -j4

Running

Algorithm implementations

MAAStar - Multi-agent A*
AACBS - Any-Angle Conflict-Based-Search
MO - Multi-Objective Conflict-Based-Search
MAPF - Conflict-Based-Search
icts - Increasing Cost Tree Search
MACBS - Meta-Agent Conflict-Based-Search with ICTS as the meta-agent solver

Test instances

There are 2 ways to set up a map:

Using map dimensions The -dimensions flag must be used followed by width, depth and height. For 2D maps height defaults to 1.
Using a map file The -mapfile flag must be followed by the path to a map relative to the root directory of hog2. See this example.

There are 3 ways to set up agent waypoints:

With an environment file and a problem file The environment file indicates the environment to use for sets of agents. See https://github.com/thaynewalker/hog2/blob/conf-avoidance/apps/MAPF/Driver.cpp#L612 The problem file indicates space-delimited waypoints in x,y,z coordinates, one agent per line. See here for an example.
With a configuration file The configuration file indicates the environment and waypoints for agents individually.
With a scenario file The scenario file is always linked to a map and indicates the map name and a single start/goal per agent. See here.

Examples

Unobstructed map with gui soved with CBS

cd build/gmake && make -j4 release && ../../bin/release/MAPF -probfile ../../test/environments/instances/8x8/10/0.csv -envfile env9.csv -dimensions 8,8,1 -radius .25

Map with obstacles icts

cd build/gmake && make -j4 release && ../../bin/release/icts -nagents 10 -scenfile ../../test/environments/instances/8x8/10/2.map.scen -mode b -agentType 9 -radius .25

RKJenamani/hog2