An Innovative Multi-Agent Search-and-Rescue Path Planning Approach
DRDC Valcartier Quebec City, Quebec Canada
Pagination or Media Count:
Search and rescue path planning is known to be computationally hard, and most techniques developed to solve practical size problems have been unsuccessful to estimate an optimality gap. A mixed-integer linear programming MIP formulation is proposed to optimally solve the multi-agent discrete search and rescue SAR path planning problem, maximizing cumulative probability of success in detecting a target. It extends a single agent decision model to a multi-agent setting capturing anticipated feedback information resulting from possible observation outcomes during projected path execution while expanding possible agent actions to all possible neighboring move directions, considerably augmenting computational complexity. A network representation is further exploited to alleviate problem modeling, constraint specification, and speed-up computation. The proposed MIP approach uses CPLEX problem-solving technology in promptly providing near optimal solutions for realistic problems, while offering a robust upper bound derived from Lagrangean integrality constraint relaxation. Modeling extension to a closed-loop environment to incorporate real-time action outcomes over a receding time horizon can even be envisioned given acceptable run-time performance. A generalized parameter-driven objective function is then proposed and discussed to suitably define a variety of user-defined objectives. Computational results reporting the performance of the approach clearly show its value.