Abstract—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.

Index Terms—Search path planning, search and rescue, linear programming.

J. Berger is with the Defence Research and Development Canada – Valcartier, Quebec City, Canada (e-mail: jean.berger@drdc-rddc.gc.ca).
N. Lo is with the T-OptLogic Ltd., Quebec City Canada (e-mail: nassirou.lo@t-optlogic.com).
M. Noel is with the Téluq, Université du Québec, Quebec City Canada (e-mail: noel.martin@teluq.uqam.ca).

Cite:Jean Berger, Nassirou Lo, and Martin Noel, "Exact Solution for Search-and-Rescue Path Planning," International Journal of Computer and Communication Engineering vol. 2, no. 3, pp. 266-271, 2013.