Distributed Task Allocation and Task Sequencing for Robotswith Motion Constraints

作     者：Sadeghi Yengejeh, Armin 

作者单位：University of Waterloo 

学位级别：master

导师姓名：Smith, Stephen Leslie

授予年度：2016年

主      题：Autonomous vehicles Distributed task allocation Nonholonomic motion planning 

摘      要：This thesis considers two routing and schedulingproblems. The first problem is task allocation and sequencing formultiple robots with differential motion constraints. Each task isdefined as visiting a point in a subset of the robot configurationspace ?– this definition captures a variety of tasks includinginspection and servicing, as well as one-in-a-set tasks. Ourapproach is to transform the problem into a multi-vehiclegeneralized traveling salesman problem (GTSP). We analyze the GTSPinsertion methods presented in literature and we provide bounds onthe performance of the three insertion mechanisms. We then developa combinatorial-auction-based distributed implementation of theallocation and sequencing algorithm. The number of the bids in acombinatorial auction, a crucial factor in the runtime, is shown tobe linear in the size of the tasks. Finally, we present extensivebenchmarking results to demonstrate the improvement over existingdistributed task allocation methods. In the second part of thisthesis, we address the problem of computing optimal paths throughthree consecutive points for the curvature-constrained forwardmoving Dubins vehicle. Given initial and final configurations ofthe Dubins vehicle and a midpoint with an unconstrained heading,the objective is to compute the midpoint heading that minimizes thetotal Dubins path length. We provide a novel geometrical analysisof the optimal path and establish new properties of the optimalDubins path through three points. We then show how our method canbe used to quickly refine Dubins TSP tours produced usingstate-of-the-art techniques. We also provide extensive simulationresults showing the improvement of the proposed approach in bothruntime and solution quality over the conventional method ofuniform discretization of the heading at the mid-point, followed bysolving the minimum Dubins path for each discreteheading