Motion planning of multiple mobile robots in formations

Abstract

Over the past few decades, multirobot systems have been studied considerably, due to their wide applications in such fields as manufacturing, surveillance, and space exploration. In many applications, robots must form and maintain formations to accomplish such complex tasks as transportation of large awkward objects, mapping, search, and rescue. Motion planning, which is one of the most important issues in multirobot formations, is significantly affected by the geometrical constraints of the formations. This thesis aims to develop a set of new motion planning methodologies for multiple mobile robots in formation-forming and formation-maintaining tasks. Studies have been performed mainly in the following two categories. First, a decentralized multirobot motion planning framework is developed to solve the formation-forming problem in a dynamic environment with limited environment information. An improved RRT (Rapidly-exploring Random Trees) based path planner is designed to update the motion planning for each robot online. When robots enter the target formation, they may constrain each other: the robot first arriving at the desired position in the formation may block the other robots from entering the formation. This thesis refers to this situation as motion conflict in the formation-forming problem. Such conflict may cause disorder among the robots or even deadlock them when they enter the formation. To overcome this problem, a dynamic priority strategy is proposed to regulate the formation-forming action in proper order. Simulations and experiments were performed on a group of mobile robots. Experimental results demonstrate that the proposed new path planner can effectively update motion planning for each robot online. By adding a dynamic priority strategy to the decentralized motion planning framework, the formation-forming goal can be achieved efficiently. Second, this thesis addresses the coordinated motion planning problem of multiple mobile robots moving along designed paths while meeting formation requirements. This problem is formulated as a velocity optimization problem, after modelling the formation relationship to be velocity-dependent. The velocity and acceleration bounds are considered so that the generated velocity profile for each robot is dynamically feasible. An objective function is established to integrate all the coordination requirements with the goal of velocity optimization, subject to various velocity constraints. A linear interactive and general optimizer (LINGO) is used to obtain an optimal motion plan offline. This plan can be further adjusted online to deal with some emergent cases, such as avoiding a suddenly appearing moving obstacle that is difficult to predict. When the moving obstacle gets close enough to the robot group, the robots need to respond by either stopping to let the obstacle pass or retreating along the previous moving trajectories. A strategy is developed to guide the robots to resume the original motion plan after collision avoidance. Simulations and experiments were performed on a group of mobile robots to verify the effectiveness of the proposed approach. This research provides a proof-of-concept demonstration of new and innovative motion planning methodologies for multiple robots in formations. Few studies have been reported in the literature regarding this topic. The research outcomes will benefit the robotics society, especially for infrastructure networks that have received considerable attention in recent years.

Date of Award	15 Jul 2010
Original language	English
Awarding Institution	City University of Hong Kong
Supervisor	Dong SUN (Supervisor)