Genetic Algorithm for In-Theatre Military Logistics Search-and-Delivery Path Planning

Authors: Jean Berger, Mohamed Barkaoui

Abstract:

Discrete search path planning in time-constrained uncertain environment relying upon imperfect sensors is known to be hard, and current problem-solving techniques proposed so far to compute near real-time efficient path plans are mainly bounded to provide a few move solutions. A new information-theoretic –based open-loop decision model explicitly incorporating false alarm sensor readings, to solve a single agent military logistics search-and-delivery path planning problem with anticipated feedback is presented. The decision model consists in minimizing expected entropy considering anticipated possible observation outcomes over a given time horizon. The model captures uncertainty associated with observation events for all possible scenarios. Entropy represents a measure of uncertainty about the searched target location. Feedback information resulting from possible sensor observations outcomes along the projected path plan is exploited to update anticipated unit target occupancy beliefs. For the first time, a compact belief update formulation is generalized to explicitly include false positive observation events that may occur during plan execution. A novel genetic algorithm is then proposed to efficiently solve search path planning, providing near-optimal solutions for practical realistic problem instances. Given the run-time performance of the algorithm, natural extension to a closed-loop environment to progressively integrate real visit outcomes on a rolling time horizon can be easily envisioned. Computational results show the value of the approach in comparison to alternate heuristics.

Keywords: Search path planning, false alarm, search-and-delivery, entropy, genetic algorithm.

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

References:

[1] S. Benkoski, M. Monticino, and J. Weisinger, "A survey of the search theory literature”, Naval Research Logistics 38, 1991, 469–494.
[2] L. Stone, Theory of Optimal Search, 2nd edition, Topics in Operations Research Series, INFORMS, 2004.
[3] Trummel, K.E. and Weisinger, J.R., "The complexity of the optimal searcher path problem”, Operations Research, 34 (2), 1986, pp.324-327.
[4] 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.
[5] T. H. Chung, J. Burdick, "Analysis of search decision making using probabilistic search strategies”, IEEE Transactions on Robotics, 28 (10), 2012, pp. 132-144.
[6] K.E. Wilson, R. Szechtman, R., M.P. Atkinson. A sequential perspective on searching for static targets, European Journal of Operational Research, 215(1), 2011, pp. 218–226.
[7] A.R Washburn. Search and Detection, 4th edn. Topics in Operations Research Series. INFORMS, 2002.
[8] Levner, E. and Kriheli, B. Search and Detection of Failed Components in Repairable Complex Systems under Imperfect Inspections, Advances in Computational Intelligence, Lecture Notes in Computer Science, Springer, Vol. 7630, 2013, pp. 399-410
[9] A. R.Washburn, "Branch and Bound Methods for a Search Problem”, Naval Research Logistics, 45, 1998, 243-257.
[10] G. Martins, A New Branch-and-Bound Procedure for Computing Optimal Search Paths. Master's Thesis. Naval Postgraduate School, 1993.
[11] 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.
[12] H. Lau, Optimal Search in Structured Environments, PhD Thesis, University of Technology, Sydney 2007.
[13] G.A. Hollinger, Search in the Physical World. CMU-RI-TR-10-20, Robotics Institute, PhD thesis, Carnegie Mellon University, 2010.
[14] 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.
[15] T. Chung, "On Probabilistic Search Decisions under Searcher Motion Constraints”, Workshop on Algorithmic Foundation of Robotics VIII, Guanajuato, Mexico. 2009, pp. 501-516.
[16] G.A. Hollinger, and S. Singh, "GSST: Anytime Guaranteed Search with Spanning Trees”, Autonomous Robots, 29(1), 2010, pp. 99-118.
[17] J.O. Royset and H. Sato, "Route Optimization for Multiple Searchers”, Naval Research Logistics, 57 (8), 2010, pp. 701-717.
[18] T. Cover, and J. Thomas, Elements of Information-Theory, 2nd edition, Wiley, 2006.
[19] Potvin, J.-Y. and Bengio, S., 1996. The Vehicle Routing Problem with Time Windows Part II: Genetic Search, INFORMS Journal on Computing 8, pp. 165–172.
[20] Goldberg, D., 1989. Genetic Algorithms in Search, Optimization, and Machine Learning. New York: Addison-Wesley.