An information theoretic based integer linear programming approach for the discrete search path planning problem

详细信息    查看全文

• 作者：Jean Berger ; Nassirou Lo ; Abdeslem Boukhtouta ; Martin Noel
• 关键词：Combinatorial optimization ; Search path planning ; Information theory ; Network flow ; Linear programming ; Open ; loop with anticipated feedback
• 刊名：Optimization Letters
• 出版年：2015
• 出版时间：December 2015
• 年：2015
• 卷：9
• 期：8
• 页码：1585-1607
• 全文大小：1,420 KB
• 参考文献：1.Agmon, N., et al.: The giving tree: constructing trees for efficient offline and online multi-robot coverage. Ann. Math. Artif. Intell. 52, 109鈥?42 (2008)MathSciNet CrossRef
  2.Benkoski, S., Monticino, M., Weisinger, J.: A survey of the search theory literature. Naval Res. Logist. 38, 469鈥?94 (1991)MATH CrossRef
  3.Chung, T.: On probabilistic search decisions under searcher motion constraints. In: Workshop on Algorithmic Foundation of Robotics VIII, Guanajuato, Mexico, pp. 501鈥?16 (2009)
  4.Choo, C., Smith, J., Nasrabadi, N.: An efficient terrain acquisition algorithm for a mobile robot. In: Proceedings of IEEE International Conference on Robotics and Automation, Sacramento, CA, pp. 306鈥?11 (1991)
  5.Cover, T., Thomas, J.: Elements of Information Theory, 2nd edn. Wiley, New York (2006)MATH
  6.Finn, A., et al.: Design challenges for an autonomous cooperative of UAVs. In: Proceedings of the International Conference on Information, Decision and Control, pp. 160鈥?69 (2007)
  7.Flint, F.E., Fernandez-Gaucherand, E., Polycarpou, M.: Efficient Bayesian methods for updating and storing uncertain search information for UAV鈥檚. In: Proceedings of 43rd IEEE Conference on Decision and Control, pp. 1093鈥?098 (2004)
  8.Hohzaki, R., Iida, K.: Optimal search plan for a moving target when a search path is given. Math. Jpn. 41(1), 175鈥?84 (1995)MATH MathSciNet
  9.Hollinger, G.A.: Search in the physical world. CMU-RI-TR-10-20, Robotics Institute. Ph.D. thesis, Carnegie Mellon University (2010)
  10.Hollinger, G.A., Singh, S.: GSST: anytime guaranteed search with spanning trees. Auton. Robots 29(1), 99鈥?18 (2010)CrossRef
  11.IBM ILOG CPLEX Optimization Studio Academic Research Edition Fix Pack 12.2.0.2. http://鈥媤ww-01.鈥媔bm.鈥媍om/鈥媠upport/鈥媎ocview.鈥媤ss?鈥媢id=鈥媠wg24028951
  12.Jin, Y., Liao, Y., Minai, A., Polycarpou, M.: Balancing search and target response in cooperative unmanned aerial vehicle (UAV) teams. IEEE Trans. Syst. Man Cybern. Part B 36(3), 571鈥?87 (2006)CrossRef
  13.Latombe, J.-C.: Robot Motion Planning, ser. International Series in Engineering and Computer Science; Robotics: Vision, Manipulation and Sensors, vol. 124. Kluwer Academic Publishers, Boston (1991)
  14.Lau, H.: Optimal search in structured environments. Ph.D. thesis, University of Technology, Sydney (2007)
  15.Lau, H., Dissanayake, G.: Probabilistic search for a moving target in an indoor environment. In: Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 3393鈥?398 (2006)
  16.Lau, H., Dissanayake, G.: Optimal search for multiple targets in a built environment. In: Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems, Edmonton, Alberta, Canada, pp. 228鈥?33 (2005)
  17.Martins, G.: A new branch-and-bound procedure for computing optimal search paths. Master鈥檚 thesis. Naval Postgraduate School (1993)
  18.Mathews, G., Durrant-Whyte, H.: Scalable decentralised control for multi-platform reconnaissance and information gathering tasks. In: 9th International Conference on Information Fusion, pp. 1鈥? (2006)
  19.Rekleitis, I., et al.: Efficient Boustrophedon multi-robot coverage: an algorithmic approach. Ann. Math. Artif. Intell. 52, 109鈥?42 (2008)MATH MathSciNet CrossRef
  20.Sankaranarayanan, A., Masuda, I.: Sensor based terrain acquisition: a new, hierarchical algorithm and a basic theory. In: Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems, Raleigh, pp. 1515鈥?523 (1992)
  21.Svennebring, J., Koenig, S.: Building terrain-covering ant robots: a feasibility study. Auton. Robots 16(3), 313鈥?32 (2004)CrossRef
  22.Stone, L.: What鈥檚 happened in search theory since the 1975 Lanchester prize? Oper. Res. 37(3), 501鈥?06 (1989)MathSciNet CrossRef
  23.Vincent, P., Rubin, I.: A framework and analysis for cooperative search using UAV swarms. In: ACM Symposium on Applied Computing, pp. 79鈥?6 (2004)
  24.Wagner, W., et al.: Distributed covering by ant-robots using evaporating traces. IEEE Trans. Robot. Autom. 15(5), 918鈥?33 (1999)CrossRef
  25.Washburn, A.R.: Branch and bound methods for a search problem. Naval Res. Logist. 45, 243鈥?57 (1998)MATH MathSciNet CrossRef
  26.Wong, S., MacDonald, B.: A topological coverage algorithm for mobile robots. In: Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems, Las Vegas, pp. 1685鈥?690 (2003)
  27.Yang, S., Luo, C., Neural, A.: Network approach to complete coverage path planning. IEEE Trans. Syst. Man Cybern. B Cybern. 34(1), 718鈥?24 (2004)CrossRef
  28.Yang, Y., Minai, A., Polycarpou, M.: Evidential map building approaches for multi-UAV cooperative search. In: Proceedings of the American Control Conference, pp. 116鈥?21 (2005)
  
• 作者单位：Jean Berger (1)
  Nassirou Lo (2)
  Abdeslem Boukhtouta (3)
  Martin Noel (4)
  
  1. DRDC Valcartier, Quebec City, Canada
  2. T-OptLogic Inc., Quebec City, Canada
  3. DRDC CORA, Ottawa, Canada
  4. UQAM, TELUQ, Quebec City, Canada
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Optimization
  Operation Research and Decision Theory
  Numerical and Computational Methods in Engineering
  Numerical and Computational Methods
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1862-4480

文摘

Discrete search path planning is known to be a NP-hard problem, and problem-solving methods proposed so far rely on heuristics with no way to reasonably estimate solution quality for practical size problems. Departing from traditional nonlinear model formulations, a novel information theoretic based approach using integer linear programming (ILP) is proposed to optimally solve the discrete open-loop centralized search path planning problem with anticipated feedback, involving a team of homogeneous agents. The approach takes advantage of objective function separability and conditional probability independence of observations to efficiently minimize expected system entropy. A network representation is exploited to simplify modeling, reduce constraint specification and speed-up problem-solving. The novelty of the approach consists in capturing false-alarm observations explicitly while proposing an original and efficient way to linearize the underlying non-linear expected entropy function required to properly represent target location uncertainty, making for the first time practical problems tractable. The proposed ILP formulation rapidly yields near-optimal solutions for realistic problems while providing for the first time, a robust lower bound through Lagrangian relaxation. Long planning problem horizon may be dynamically adapted by periodically solving new problem instances incorporating actual observation outcomes from previous episodes over receding horizons. Computational results clearly show the value of the approach in comparison to a myopic heuristic over various problem instances. Keywords Combinatorial optimization Search path planning Information theory Network flow Linear programming Open-loop with anticipated feedback