Receding Horizon Optimization Method for Solving the Cops and Robbers Problems in a Complex Environment with Obstacles
- PDF / 2,101,583 Bytes
- 30 Pages / 595.224 x 790.955 pts Page_size
- 46 Downloads / 158 Views
Receding Horizon Optimization Method for Solving the Cops and Robbers Problems in a Complex Environment with Obstacles Categories (2), (5) Qiang Zhu1 · Kexin Wang1 · Zhijiang Shao1 · Lorenz T. Biegler2 Received: 24 January 2019 / Accepted: 18 March 2020 © Springer Nature B.V. 2020
Abstract Cops and Robbers problems are classical examples of pursuit and evasion problems which are parts of key researches in the field of robotics. This study shall specifically focus on the evasion strategies of robbers. This study presents the receding horizon optimization method to obtain such strategies of robbers and solves the Cops and Robbers problems in a complex environment with obstacles. In this method, the robbers estimate the control variables of the cops in real time to address the difficulties in obtaining the complete pursuit strategies of the latter for solving the evasion strategies. This method also guarantees the real-time solutions of receding horizon optimization problems. Orthogonal collocation is utilized to discretize the Cops and Robbers dynamic model, and then the resulting nonlinear programming problem is solved to obtain the optimal control. To improve the accuracy of the solution, we propose an iterative hp-adaptive mesh refinement strategy to satisfy the optimality conditions by adjusting the number of finite elements and the order of Lagrange polynomials. This mesh refinement strategy also iteratively uses finite elements and collocation points as well as applies the finite element merging strategy to improve the solution efficiency. The proposed method also provides a framework for solving other pursuit and evasion problems in a complex environment with obstacles. Keywords Cops and Robbers problems · Complex environment with obstacles · Iterative hp-adaptive mesh refinement · Orthogonal collocation method · Receding horizon optimization
1 Introduction Cops and Robbers problems are classical benchmarks of moving target search and pursuit and evasion problems which are branches of focus researches in the field of robotics [1]. In these problems, cops pursue robbers, meanwhile, robbers must evade cops and simultaneously pursue moving or fixed targets in a specified environment. Because these problems are widely observed in nature and play critical roles in the artificial world, Cops and Robbers
Zhijiang Shao
[email protected] 1
College of Control Science and Engineering, Zhejiang University, Hangzhou, 310027, China
2
Department of Chemical Engineering, Carnegie Mellon University, Pittsburgh, PA 15213, USA
problems have attracted much attention of researchers. They are introduced into the artificial intelligence literature by Ishida and Korf [2] as a new variant of classical search problems. Many strategies for cops have been proposed to catch moving robbers efficiently [3–5]. These problems have been successfully applied to military struggles, sports competitions and social services based on robots [1, 6, 7]. Although the strategies for cops (pursuers) have been greatly developed in the previous rese
Data Loading...
