A New Multi-Target, Multi-Agent Search-and-Rescue Path Planning Approach

Authors: Jean Berger, Nassirou Lo, Martin Noel

Abstract:

Perfectly suited for natural or man-made emergency and disaster management situations such as flood, earthquakes, tornadoes, or tsunami, multi-target search path planning for a team of rescue agents is known to be computationally hard, and most techniques developed so far come short to successfully estimate optimality gap. A novel mixed-integer linear programming (MIP) formulation is proposed to optimally solve the multi-target multi-agent discrete search and rescue (SAR) path planning problem. Aimed at maximizing cumulative probability of successful target detection, it captures anticipated feedback information associated with possible observation outcomes resulting from projected path execution, while modeling agent discrete actions over all possible moving directions. Problem modeling further takes advantage of network representation to encompass decision variables, expedite compact constraint specification, and lead to substantial problem-solving speed-up. The proposed MIP approach uses CPLEX optimization machinery, efficiently computing near-optimal solutions for practical size problems, while giving a robust upper bound obtained from Lagrangean integrality constraint relaxation. Should eventually a target be positively detected during plan execution, a new problem instance would simply be reformulated from the current state, and then solved over the next decision cycle. A computational experiment shows the feasibility and the value of the proposed approach.

Keywords: Search path planning, search and rescue, multi-agent, mixed-integer linear programming, optimization.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1093289

References:

[1] K.E.Trummel and J.RWeisinger, "The complexity of the optimal searcher path problem”,Operations Research, 34 (2), 1986, pp.324-327.
[2] S. Benkoski, M. Monticino, and J. Weisinger, "A survey of the search theory literature”, Naval Research Logistics 38, 1991, 469–494.
[3] L. Stone, "What’s happened in search theory since the 1975 Lanchester Prize?”, Operations Research, 37 (3), 1989.
[4] R. Hohzaki, and K. Iida, "Optimal search plan for a moving target when a search path is given”, Math. Japonica, 41(1), 1995, pp. 175-184.
[5] H. Lau, Optimal Search in Structured Environments, PhD Thesis, University of Technology, Sydney 2007.
[6] H. Lau, and G. Dissanayake, "Probabilistic search for a moving target in an indoor environment”, in Proc. IEEE/RSJ Int. Conf. Intelligent Robots and Systems, 2006, pp. 3393-3398.
[7] H. Lau, and G. Dissanayake, "Optimal search for multiple targets in a built environment”, in Proc. IEEE/RSJ Int. Conf. Intelligent Robots and Systems, Edmonton, Alberta, Canada, 2005, pp. 228-233.
[8] J.-C. Latombe, Robot Motion Planning, ser. International Series in Engineering and Computer Science; Robotics: Vision, Manipulation and Sensors, vol. 124, Boston, Kluwer Academic Publishers, 1991.
[9] C. Choo, J. Smith, and N. Nasrabadi, "An efficient terrain acquisition algorithm for a mobile robot”, in Proc. IEEE Int. Conf. Robotics and Automation, Sacramento, CA, 1991, pp. 306–311.
[10] A. Sankaranarayanan, and I. Masuda, "Sensor based terrain acquisition: A new, hierarchical algorithm and a basic theory”, in Proc. IEEE/RSJInt. Conf. Intelligent Robots and Systems, Raleigh, 1992, pp. 1515–1523.
[11] J. Svennebring, and S. Koenig, "Building terrain-covering ant robots: A feasibility study”, Auton. Robots, 16 (3), 2004, pp. 313–332.
[12] S. Wong, and B. MacDonald, "A topological coverage algorithm for mobile robots”, in Proc. IEEE/RSJ Int. Conf. Intelligent Robots and Systems, Las Vegas, 2003, pp. 1685–1690.
[13] S. Yang, and C. Luo, "A neural network approach to complete coverage path planning”, IEEE Trans. Syst.,Man, Cybern. B, Cybern., 34(1), 2004, pp. 718–724.
[14] I. Rekleitis, et al., "Efficient boustrophedon multi-robot coverage:an algorithmic approach”, Ann Math Artif. Intell. 52, 2008, pp. 109–142.
[15] W. Wagner, et al., "Distributed covering by ant-robots using evaporating traces”, IEEE Trans. Robot. Autom., 15(5), 1999,pp. 918-933.
[16] J.O. Royset and H. Sato, "Route Optimization for Multiple Searchers”, Naval Research Logistics, 57 (8), 2010, pp. 701-717.
[17] T. H. Chung, J. Burdick, "Analysis of search decision making using probabilistic search strategies”, IEEE Transactions on Robotics, 28 (10), 2012, pp. 132-144.
[18] Y. Jin, Y. Liao, A. Minai, and M. Polycarpou, "Balancing search and target response in cooperative unmanned aerial vehicle (UAV) Teams”, IEEE Trans on Sys Man and Cybern. Part B, 36(3), 2006, pp. 571-587.
[19] G.A. Hollinger, Search in the Physical World. CMU-RI-TR-10-20, Robotics Institute, PhD thesis, Carnegie Mellon University, 2010.
[20] T. Chung, "On Probabilistic Search Decisions under Searcher Motion Constraints”, Workshop on Algorithmic Foundation of Robotics VIII, Guanajuato, Mexico. 2009, 501-516.
[21] G.A. Hollinger, and S. Singh, "GSST: Anytime Guaranteed Search with Spanning Trees”, Autonomous Robots, 29(1), 2010, pp. 99-118.
[22] A. R.Washburn, "Branch and Bound Methods for a Search Problem”, Naval Research Logistics,45, 1998, 243-257.
[23] J. Berger, N. Lo, and M. Noel,Exact Solution for Search-and-Rescue Path Planning, Proceedings of the 2nd International Conference on Information Computer Applications, Rome, Italy, February 2013.
[24] IBMILOG CPLEX Optimizer, Available: http://www-01.ibm.com/software/integration/optimization/cplex-optimization-studio/cplex-optimizer/cplex-performance/ and IBM ILOG CPLEX V12.1, 2009. Available: ftp://public.dhe.ibm.com/software/websphere/ ilog/docs/optimization/cplex/ps_usrmancplex.pdf
[25] M. Morin et al. "The Optimal Searcher Path problem with a Visibility Criterion in Discrete Time and Space”, Int. conference on Information Fusion, Seatle, USA, 2009.
[26] M. Morin, A.P. Papillon, F. Laviolette, I. Abi-Zeid, and C.G. Quimper, "Constraint Programming for Path Planning with Uncertainty: Solving the Optimal Search Path problem,” in Proceedings of the 18th Conference on Principles and Practice of Constraint Programming, Québec, Qc, Canada, 2012, pp. 988-1003.
[27] J. N Eagle., and J. R Yee., "An optimal branch and bound procedure for the constrained path, moving target search problem”, Operations Research, vol. 38, no. 1, 1990, pp. 110-114.
[28] R. F Dell, J. N Eagle, G. H. Martins and A. G. Santos, "Using multiple searchers in constrained-path, moving-target search problems”, Naval Research Logistics, vol. 43, 1996, 463-480.
[29] N. Lo, J. Bergerand M. Noel, Toward Optimizing Static Target Search Path Planning, Proceedings of the 5th IEEE Symposium on Computational Intelligence for Security and Defence Applications, Ottawa, Canada, July 2012.