טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentCons Matthew
SubjectIntegrating Task and Motion Planning for Unmanned Aerial
Vehicles
DepartmentDepartment of Aerospace Engineering
Supervisors Professor Tal Shima
Professor Carmel Domshlak
Full Thesis textFull thesis text - English Version


Abstract

In this thesis, the process of integrating task and motion planning for unmanned aerial vehicles is examined. Here, an unmanned aerial vehicle is modeled as a Dubins vehicle: a vehicle with a minimum turn radius and the inability to go backward. Given a starting position and orientation for a Dubins vehicle and a set of stationary targets, the main problem is to determine the shortest flyable path that visits each target. This is called the Dubins traveling salesman problem, an extension of the well-known traveling salesman problem. Algorithms with different approaches, including a hierarchical approach, a generalized traveling salesman problem reformulation approach, and a search with an upper bound Dubins cost approach, are developed and contrasted. Monte Carlo simulations are performed for a range of vehicle turn radii. Simulations results show that integrating two plausible kinematic satisfying paths as an upper bound to determine the cost-so-far into a search algorithm generally improves performance in terms of the shortest path cost and search complexity. Furthermore, when a suitable trajectory for traversing an ordered set of targets has been found, the applicability of using proportional navigation guidance is examined. It is shown that using a simple proportional navigation guidance law, stationary targets located within the vehicle's turn circle are unreachable. To address this issue, waypoints are generated that will allow the vehicle to reach these hard targets with minimum distance. The waypoints are generated by solving a relaxed version of the point-to-point Dubins problem. In addition, it is shown that any trajectory composed of point-to-point Dubins paths can be navigated using proportional navigation with a minimum number of waypoints, regardless of the target positions.