Full Record

New Search | Similar Records

Author
Title Discrete Path Planing Strategies for Coverage and Multi-Robot Rendezvous
URL
Publication Date
University/Publisher University of Waterloo
Abstract This thesis addresses the problem of motion planning for autonomous robots, given a map and an estimate of the robot pose within it. The motion planning problem for a mobile robot can be defined as computing a trajectory in an environment from one pose to another while avoiding obstacles and optimizing some objective such as path length or travel time, subject to constraints like vehicle dynamics limitations. More complex planning problems such as multi-robot planning or complete coverage of an area can also be defined within a similar optimization structure. The computational complexity of path planning presents a considerable challenge for real-time execution with limited resources and various methods of simplifying the problem formulation by discretizing the solution space are grouped under the class of discrete planning methods. The approach suggests representing the environment as a roadmap graph and formulating shortest path problems to compute optimal robot trajectories on it. This thesis presents two main contributions under the framework of discrete planning. The first contribution addresses complete coverage of an unknown environment by a single omnidirectional ground rover. The 2D occupancy grid map of the environment is first converted into a polygonal representation and decomposed into a set of convex sectors. Second, a coverage path is computed through the sectors using a hierarchical inter-sector and intra-sector optimization structure. It should be noted that both convex decomposition and optimal sector ordering are known NP-hard problems, which are solved using a greedy cut approximation algorithm and Travelling Salesman Problem (TSP) heuristics, respectively. The second contribution presents multi-robot path-planning strategies for recharging autonomous robots performing a persistent task. The work considers the case of surveillance missions performed by a team of Unmanned Aerial Vehicles (UAVs). The goal is to plan minimum cost paths for a separate team of dedicated charging robots such that they rendezvous with and recharge all the UAVs as needed. To this end, planar UAV trajectories are discretized into sets of charging locations and a partitioned directed acyclic graph subject to timing constraints is defined over them. Solutions consist of paths through the graph for each of the charging robots. The rendezvous planning problem for a single recharge cycle is formulated as a Mixed Integer Linear Program (MILP), and an algorithmic approach, using a transformation to the TSP, is presented as a scalable heuristic alternative to the MILP. The solution is then extended to longer planning horizons using both a receding horizon and an optimal fixed horizon strategy. Simulation results are presented for both contributions, which demonstrate solution quality and performance of the presented algorithms.
Subjects/Keywords motion planning; coverage; multi-robot surveillance; autonomous mobile robots; vehicle routing; scheduling and coordination
Language en
Country of Publication ca
Record ID handle:10012/8169
Repository waterloo
Date Retrieved
Date Indexed 2020-08-12

Sample Search Hits | Sample Images

…7 1.2 Illustration of the multi-robot recharging problem . . . . . . . . . . . . . . 8 2.1 Coverage planning algorithm flowchart . . . . . . . . . . . . . . . . . . . . 14 2.2 Greedycut decomposition of non-convex vertices…

…task, such as surveillance or exploration and enable the robot to interpret it into a set of low-level functions of motion, sensing and actuation to accomplish the task. This thesis focusses on autonomous motion planning, which is an active area of…

…involve visiting a set of vertices in a graph can be modelled as variants of the TSP. Multi-robot path planning problems can be similarly represented as TSP variants such as the Multiple Travelling Salesman Problem (MTSP), Multiple Generalized…

…Noon-Bean Transformation to solve GTSP instances and also presents a novel adaptation of the Noon-Bean method for MGTSP solutions to Multi-robot path planning problems. In general, the discrete path planning framework involves discretizing the problem…

…concern two different classes of planning problems. The first contribution addresses complete coverage of an unknown environment by a single omnidirectional ground rover and the second presents a multi-robot path planning strategy for optimally scheduled…

…resulting path are presented and compared to existing coverage approaches. 1.3.2 Multi-robot Rendezvous for Autonomous Recharging Coordinated teams of autonomous robots are often proposed as a means to continually monitor changing environments in…

…the problem is to position multi-robot persistent recharging in the space of graph-based optimal path planning problems formulated using mixed integer linear programs. Based 7 Figure 1.2: A sample scenario with coordinated UAVs performing a…

…robots to meet the working robots along their trajectories and recharge them as needed. The main contributions are the following. (i) The idea of multi-robot recharging in dynamic persistent tasks using dedicated teams of mobile charging…

.