Multi-robot sweep coverage and motion planning

• Main Author: Cao, Muqing
• Other Authors: Xie Lihua
• Format: Thesis-Doctor of Philosophy
• Language: English
• Published: Nanyang Technological University 2023
• Subjects: Engineering::Electrical and electronic engineering::Control and instrumentation::Robotics; Engineering::Electrical and electronic engineering::Control and instrumentation::Control engineering
• Online Access: https://hdl.handle.net/10356/168385
• Institution: Nanyang Technological University

Multi-robot systems have received increasing attention from both research community and engineering practitioners due to their broad application scenarios. In particular, multiple robots can be deployed to cover a target region to conduct quality inspection, surveillance, search and rescue. This thesis focuses on two important aspects of multi-robot coverage problem: high-level coverage planning, which aims to partition the target region or allocate coverage workloads among the robots; and low-level motion planning, which aims to generate smooth trajectory for each robot that avoids the static and dynamic obstacles. For high-level coverage planning, we focus on the problem of sweep coverage over a region with uneven and unknown workload distribution. Uneven workload distribution means that a robot has to spend different amounts of time covering a unit area at different locations in the region. Unknown workload distribution necessitates the online allocation of workload among the robots. To tackle this problem, we adopt the formulation in which the entire region is separated into multiple stripes, and a discrete-time distributed workload allocation algorithm is used to allocate workload on the stripe to each robot. The convergence of the distributed workload allocation algorithm to the optimal workload assignment is established, error bounds between the actual completion time and the optimal completion time are derived. Furthermore, we consider the scenario when the robots have limited workload sensing ranges and propose a new algorithm to address this scenario with proven stability. Realistic simulations and actual flight experiments using UAVs are carried out to demonstrate the practicality and validate the theoretical results. The research described above aims to achieve optimal workload assignments among the robots, which do not guarantee optimal coverage completion time. As a further step towards the time-optimal coverage planning problem, we propose an improved workload partition algorithm and prove that the operation time on each stripe converges to the minimum under the discrete-time update law. We conduct comprehensive simulation studies and compare our method with the existing methods to verify the theoretical results and the advantage of the proposed method. Flight experiments on mini drones are also conducted to demonstrate the practicality of the proposed algorithm. While the high-level planning module generates target positions or moving directions for the robots, the low-level motion planning module generates dynamically feasible and collision-free trajectories leading to the target position. To build a reliable motion planning module for multiple robots, we propose a differential dynamic programming (DDP) based method for polynomial trajectory generation for differentially flat systems. In particular, we take a new perspective from state-space representation and convert the constrained trajectory generation problem (both with and without time optimization) to a discrete-time finite-horizon optimal control problem with inequality constraints. The proposed method is combined with a decentralized multi-robot planning framework to generate safe and dynamically feasible trajectories for the robots to follow. Both numerical comparisons with state-of-the-art methods and physical experiments are presented to verify and validate the effectiveness of our theoretical findings. Since a coverage mission may last for an extended period of time, tethered systems are commonly employed to extend the working duration of mobile robots. Hence, based on the above research, we further investigate the motion planning problem of multiple tethered robots and present a complete approach to address this problem. Firstly, we present a procedure to set up a multi-robot tether-aware representation of homotopy, using which we can efficiently evaluate the feasibility and safety of a potential path in terms of (1) the cable length required to reach a target following the path, and (2) the risk of entanglements with the cables of other robots. Then, the proposed representation is applied in the decentralized planning framework to generate entanglement-free, collision-free and dynamically feasible trajectories. The efficiency of the proposed homotopy representation is shown in comparison with existing single and multiple tethered robot planning approaches. Simulation and flight experiments demonstrate the effectiveness of the approach in entanglement prevention and real-time implementation.