Volume 2 Number 3 (May 2013)
Home > Archive > 2013 > Volume 2 Number 3 (May 2013) >
IJCCE 2013 Vol.2(3): 266-271 ISSN: 2010-3743
DOI: 10.7763/IJCCE.2013.V2.185

Exact Solution for Search-and-Rescue Path Planning

Jean Berger, Nassirou Lo, and Martin Noel
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.

General Information

ISSN: 2010-3743 (Online)
Abbreviated Title: Int. J. Comput. Commun. Eng.
Frequency: Quarterly
Editor-in-Chief: Dr. Maode Ma
Abstracting/ Indexing: INSPEC, Google Scholar, Crossref, EBSCO, ProQuest, and Electronic Journals Library
E-mail: ijcce@iap.org
  • Jun 20, 2019 News!

    IJCCE Vol. 6, No. 3 - Vol. 7, No. 3 have been indexed by EI (Inspec) Inspec, created by the Institution of Engineering and Tech.!   [Click]

  • Sep 16, 2021 News!

    IJCCE Vol.10, No.4 is published with online version!   [Click]

  • Jun 10, 2021 News!

    IJCCE Vol.10, No.3 is published with online version!   [Click]

  • Mar 12, 2021 News!

    IJCCE Vol.10, No.2 is published with online version!   [Click]

  • Dec 09, 2020 News!

    IJCCE Vol.10, No.1 is published with online version!   [Click]

  • Read more>>