Exact Solution for Search-and-Rescue Path Planning
Jean Berger, Nassirou Lo, Martin Noël · International Journal of Computer and Communication Engineering · 2013
Discrete search and rescue path planning is known to be hard, and problem-solving techniques proposed so far mainly fail to properly assess optimality gap for practical size problems.A new mixed-integer linear programming (MIP) formulation is proposed to optimally solve the single agent discrete search and rescue (SAR) path planning problem.The approach lies on a compact open-loop SAR with anticipated feedback problem model to efficiently maximize cumulative probability of success in detecting a target.Anticipated feedback information resulting from possible observations outcomes along the path is exploited to update target occupancy beliefs.A network representation is utilized to simplify modeling, facilitate constraint specification and speed-up problem-solving.The proposed MIP approach rapidly yields optimal solutions for realistic problems using parallel processing CPLEX technology, while providing for the first time a robust upper bound on solution quality through Lagrangean integrality constraint relaxation.Fast computation naturally allows extending open-loop modeling to a closed-loop environment to progressively integrate real-time action outcomes as they occur on a rolling time horizon.Comparative performance results clearly show the value of the approach.