Full Record

Author | Mathew, Neil |

Title | Discrete Path Planing Strategies for Coverage and Multi-Robot Rendezvous |

URL | http://hdl.handle.net/10012/8169 |

Publication Date | 2014 |

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 | 2020-08-07 |

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…