Candidate: Frank Imeson
Title: Robotic Path Planning for High-Level Tasks in Discrete Environments
Date: February 1, 2018
Time: 4:00 PM
Place: EIT 3142
Supervisor(s): Smith, Stephen L.
Abstract:
This seminar proposes two techniques for solving high-level multi-robot motion planning problems. We focus on an important class of problems that require an allocation of spatially distributed tasks to robots, along with a set of efficient paths for the robots to visit their task locations.
The first technique, SAT-TSP models the problem with a framework that allows a natural coupling between the allocation problem and the path planning problem. The allocation problem is encoded as a Boolean Satisfiability problem (SAT) and the path planning problem is encoded as a Travelling Salesman Problem (TSP). We propose an algorithm that leverages recent advances in Satisfiability Modulo Theory (SMT) to combine state-of-the-art SAT and TSP solvers. We evaluate the approach on a series of patrolling, periodic routing, and multi-robot sample collection problems. The results show that our algorithm outperforms a commercial grade mathematical programming solver on a majority of the problems, especially the more difficult problems.
The second set of techniques, is used in conjunction with existing path planning solvers to prune solutions from the search space and consequently improve solver efficiency. We propose two approaches for pruning solutions: a coupled method and a hierarchical method. Both approaches rely on a clustering method we developed called Gamma-Clustering, which is used to ensure, solutions found by either approach are within a constant factor of the optimal. We demonstrate the effectiveness of these approaches on travelling salesman instances, sample collection problems, and period routing problems. Additionally, we compare the quality of Gamma-Clusterings to clusterings found by other methods. The results show that for many instances we significantly improve solver efficiency with little to no reduction in solution quality. Additionally, the results show that as instances become more difficult these approaches can be used to find higher quality solutions than a standard approach that does not use clusters.