טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentGottlieb Yoav
SubjectTask Assignment and Motion Planning in the Presence of
Obstacles
DepartmentDepartment of Aerospace Engineering
Supervisor Professor Tal Shima


Abstract

In this thesis we address the integrated task assignment and motion planning problem of assigning a team of aerial or ground vehicles to cooperatively perform tasks on multiple stationary targets scattered in a 2D environment with obstacles. The targets need to be serviced possibly with some (time varying) level of priority.

Task assignment and motion planning are coupled. This is because the assignment allocation process depends on the actual paths the vehicles take, which in turn depends on the motion planning. On the other hand, the vehicle's trajectory depends not only on the current target to visit but also depends on which target is visited next, as it directly affects the length of the vehicle's path. The targets order of visit is the product of the task assignment process.

The aerial and ground vehicles considered in this work are assumed to have a limited radius of turn, and are represented by the Dubins and Reeds-Shepp vehicle models, respectively. By using the relaxed Dubins and Reeds-Shepp paths (that do not enforce a final heading constraint) we were able to generate vehicle trajectories from each target to the next that are independent of the following targets. This attribute enabled us to use a hierarchical approach to solve the coupled task assignment and motion planning in an integrated fashion.

The integrated problem is posed in the form of a decision tree and two search algorithms are proposed to provide solutions to this problem. An exhaustive search algorithm, which improves over run time and provides the minimum cost solution encoded in the tree, and a greedy algorithm that provides a quick feasible solution.

As the task assignment solution depends on the underlying motion planning for generating the vehicle's feasible path, we provide motion planning solutions, based on relaxed paths, considering static obstacles, set of targets, and possibly a timing constraint.

The motion planning sub-problem is posed in the form of a search tree, and two deterministic search algorithms are presented to solve the problem at hand. A quick heuristic greedy algorithm, which uses the visibility graph Euclidean distances for a proper approximation of the remaining vehicle path, and an exhaustive algorithm which provides the best solution encoded in the tree. Due to the high computational complexity of the multi-target scenario, a genetic algorithm is also proposed. The target timing constraint is addressed by using a developed path elongation algorithm amidst obstacles.

The performance of the algorithms is demonstrated and compared through sample runs and a Monte Carlo study. Results confirm that the heuristic algorithm provides relatively good solutions in a short run time for a vehicle with a small turn radius, while the genetic algorithm offers a good tradeoff between computational load and performance in a highly cluttered environment or when the vehicle turn radius is large.