Information Driven Multi-Agent Path Finding

Jake Olkin*, Viraj Parimi*, Brian Williams
Massachusetts Institute of Technology
*Equal contribution
IROS 2024

Project: info-mapf-mers.csail.mit.edu • Paper: arXiv:2409.13065

This repo is for the information driven MAPF problem, where, given a set of agents, some phenomenon of interest, and a map of the area, we compute the path over all agents that gathers the most information.

Overview of Method

This method uses a simple A* style search, however the innovation lies in how we estimate the heuristic functions, and how we can exploit the structure of the problem to prune unnecessary paths.

Simply put, we want our path to maximize the information gain from the observations taken along the way. A given node in the search tree represents a path prefix for each agent. We can use this to calculate the information gain of these partial paths. Then, we can create an optimistic heuristic for the maximum information gain from calculating the best information gain for each agent individually, and then just summing them together.

Testing Information

In our tests, we will have a discritized grid for the agents to traverse, moving in the cardinal directions. To represent the relationship between the phenomenon and the measured features, we will use gaussian processes.

This makes the assumption that, when the mean value for a gaussian process at a given location is above a certain threshold, we will model that the probability that the phenomenon also appears at that location is high. Whereas, if we do not meet that threshold, we will model that the probability that the phenomenon also appears as quite low.

We will therefore supply a map with at least one phenomenon placed on it, and then use it as the center for a gaussian process. The feature at each cell will be a function of the distance between the phenomenon and the measured cell. Then we will add measurement noise on top of that when we take a measurement to get the measured value.

We will also be assuming, for our testing, that we are dealing with continuous measurements. This is what allows us to use the gaussian process assumptions listed prior.

Requirements

conda env create -f environment.yml

Experiments

Small Examples

cd test
python test_rh_ma_vulcan.py --type <problem_type>

MAPF Suite

cd test
python test_mapf_suite --map_type <map_type>

Real World Datasets

cd test
python test_real_world_setup.py --dataset_name <name_of_dataset> --cell_size_degrees <discretization_factor>

Note: Information about the program options can be found in the corresponding files.

Citation

If you use our work or codebase in your research, please cite our paper.

@INPROCEEDINGS{10801571,
  author={Olkin, Jake and Parimi, Viraj and Williams, Brian},
  booktitle={2024 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)}, 
  title={Multi-Agent Vulcan: An Information-Driven Multi-Agent Path Finding Approach}, 
  year={2024},
  volume={},
  number={},
  pages={10253-10259},
  keywords={Additives;Markov decision processes;Path planning;Collision avoidance;Autonomous vehicles;Mutual information;Intelligent robots},
  doi={10.1109/IROS58592.2024.10801571}
}