Mixed-Integer Linear Programming Models for Multi-Robot Non-Adversarial Search

Beatriz A. Asfora, Jacopo Banfi, Mark E. CampbellIEEE RA-L 2020 · DOI

TL;DR

This paper introduces the first Mixed-Integer Linear Programming (MILP) models for the Multi-Robot Efficient Search Path Planning (MESPP) problem, enabling more efficient and general solutions than previous methods. These MILP models significantly reduce computation time, allowing for longer planning horizons and better scalability, even in the presence of complex factors like arbitrary capture ranges and false negatives.

What Problem Does This Paper Address?

The Multi-Robot Efficient Search Path Planning (MESPP) problem involves a team of robots searching for a moving, non-adversarial target within a given deadline in a graph-represented environment. The goal is to find a set of paths for the robots that maximizes the probability of intercepting the target. Previous state-of-the-art approaches relied on path enumeration, which suffers from exponential complexity with respect to the number of robots and planning horizon. This limits their practical application to short planning horizons and simple scenarios. This paper addresses this by proposing MILP models that can handle multiple searchers, arbitrary capture ranges, and false negatives, while offering significantly improved computational performance.

Methods

The core contribution of this paper is the development of novel Mixed-Integer Linear Programming (MILP) models for the MESPP problem. These models leverage the power of modern MILP solvers, which employ sophisticated branching and pruning techniques, to find optimal or near-optimal solutions more efficiently than traditional path enumeration.

The authors present three MILP models, progressively increasing in generality:

  1. SV-MILP (Same-Vertex Capture, No False Negatives): This model handles scenarios where robots can only detect the target if they are in the same vertex and have perfect sensing.
  2. MV-MILP (Multi-Vertex Capture, No False Negatives): This model extends the first to allow robots to detect targets within a certain range, still assuming perfect sensing.
  3. FN-MV-MILP (False Negatives, Multi-Vertex Capture): This is the most general model, incorporating arbitrary capture ranges and accounting for false negatives in the robots' sensing capabilities.

The paper also details how these models can be adapted for a distributed, receding-horizon planning scheme, mirroring the implicit coordination approach from prior work but using MILP for single-robot path optimization. This distributed approach significantly improves scalability for larger teams.

Datasets

The paper does not introduce new datasets. Instead, it uses existing graph environments from prior work:

  • OFFICE: A graph environment representing a room layout.
  • MUSEUM: Another graph environment representing a room layout.
  • GRID: A 10x10 grid graph.

These environments are used to evaluate the performance of the proposed MILP models under various conditions, including different team sizes, planning horizons, and the presence of false negatives.

Key Insights and Ideas

  • NP-Hardness of MESPP: The paper formally proves that the MESPP problem is NP-hard, even in simplified cases (grid graph, stationary target, single searcher). This justifies the need for efficient optimization techniques beyond brute-force enumeration.
  • MILP as a Powerful Paradigm: The adoption of MILP for MESPP unlocks the potential of advanced solvers, leading to dramatic improvements in computational efficiency and enabling more complex problem formulations.
  • Scalability Breakthrough: The MILP-based approach, particularly when combined with a distributed planning strategy, offers a significant leap in scalability compared to previous methods, allowing for larger teams and longer planning horizons without prohibitive computation times.
  • Impact of False Negatives: The models effectively incorporate false negatives, demonstrating that while they increase computational complexity, the MILP framework can still manage these uncertainties.
  • Trade-off Between Optimality and Time: The simulations highlight the inherent trade-off between achieving optimal solutions and the time required to compute them, especially for complex scenarios. The distributed MILP approach offers a practical balance for real-time applications.

Key Results

  • Computational Speedup: The MILP approach achieves up to a 98% decrease in computational time compared to the previous state-of-the-art algorithm for distributed planning.
  • Near-Optimal Distributed Solutions: The distributed MILP approach yields solutions that are within 6% of the optimal offline solution in terms of mission time, while requiring significantly less computation.
  • Handling Complexity: The models successfully handle multiple searchers, arbitrary capture ranges, and false negatives simultaneously.
  • Scalability: For a team of 5 robots, the distributed MILP approach scales much better than the centralized approach, with median solution times increasing only 3x compared to a 3400x increase for the centralized method.
  • Planning Horizon: The MILP models enable longer planning horizons. For example, for a single searcher, planning horizons up to 16 are solvable within reasonable time limits for simpler environments.

Limitations and Future Work

  • Numerical Issues: The authors note that very rarely, MILP solvers might encounter numerical issues with very small probabilities, deeming the problem infeasible. This can be addressed by disabling the presolver or re-planning at the next time step.
  • Communication Constraints: The current distributed approach does not explicitly address communication constraints between robots.
  • Heterogeneous Teams: Future work aims to generalize the models to handle heterogeneous teams of searchers (e.g., humans, ground vehicles, aerial vehicles).
  • Connectivity Constraints: Incorporating connectivity constraints into the planning process is another avenue for future research.

Summary updated

BibTeX
@article{asfora2020mixed,
  author = {Beatriz A. Asfora and Jacopo Banfi and Mark E. Campbell},
  title = {{Mixed-Integer Linear Programming Models for Multi-Robot Non-Adversarial Search}},
  journal = {IEEE RA-L},
  year = {2020},
  doi = {10.1109/lra.2020.3017473},
}
Figure