Download or read book Multi-robot Optimal Motion Planning written by Guoxiang Zhao and published by . This book was released on 2022 with total page 0 pages. Available in PDF, EPUB and Kindle. Book excerpt: The recent rapid development of computing, communication and sensing technologies triggers the prevalence of multi-robot systems. Compared to single-robot systems, multi-robot systems are advantageous in three aspects: 1) they can accomplish tasks which are beyond the capabilities of single robots; 2) they are cheaper and more flexible for certain tasks; 3) control scheme of multi-robot systems may reveal insights into key issues in social and life sciences. Multi-robot systems have numerous applications in various areas, such as traffic coordination and precision agriculture. Robotic motion planning is a fundamental problem where a sequence of controls are identified to steer robots to goal regions subject to geometric and dynamic constraints. However, the problem is computationally hard even for a single robot. The generalized mover's problem is shown to be PSPACE-hard in degrees of freedom. The optimal motion planning, where the aggregate cost along the returned trajectory is minimized, is more computationally challenging. It is shown that computing the shortest path in R^3 populated with obstacles is NP-hard in the number of obstacles. Multi-robot motion planning is even harder than its single-robot counterpart and its worst-case computational complexity grows exponentially in the number of robots. In this dissertation, we aim to study multi-robot optimal motion planning and design a set of planners towards scalability and optimality. Our research is three-fold. We first investigate the scenario where a team of robots desire to arrive at their own goal regions as soon as possible. The robots are governed by complex dynamics and need to maintain safe distance from static obstacles and other robots. The optimality of the solution is characterized by Pareto optimality, where the reduction of one robot's travelling time must cause the rise of others'. A novel numerical algorithm is proposed to identify the Pareto optimal solutions where no robot can unilaterally reduce its traveling time without extending others'. The consistent approximation of the algorithm in the epigraphical profile sense is guaranteed using set-valued numerical analysis. Experiments on an indoor multi-robot platform and computer simulations show the anytime property of the proposed algorithm; i.e., it is able to quickly return a feasible control policy that safely steers the robots to their goal regions and it keeps improving policy optimality if more time is given. Then we propose a distributed algorithm to achieve much better scalability. Specifically, the algorithm integrates decoupled optimal feedback planning and distributed conflict resolution to coordinate a fleet of unicycle robots. Each robot independently generates its optimal motions offline and avoids collisions with other objects in online execution. The computational complexity is independent of the robot number. Moreover, each robot's individual planner is optimal and its motion is rarely interfered in exercise, so the algorithm is near-optimal. Collision avoidance and finite-time arrival at the goal regions are formally guaranteed. A set of simulations are conducted to verify the scalability and near-optimality of the proposed algorithm. Lastly, we propose a distributed optimal motion planning algorithm for heterogeneous multi-robot systems and strongly coupled missions to balance scalability and optimality, where multiple robots of different dynamics desire to safely reach their respective goal regions with minimal cost. Each robot shares its policy with others in parallel and takes best response with respect to others' policies in a sequential fashion. The proposed algorithm is shown to converge to the optimal value function, and the computational complexity is linear with respect to robot number but is much smaller than benchmark. A set of simulations are conducted to verify the scalability and near-optimality of the proposed algorithm.