Task Assignment and Motion Planning in the Presence of Obstacles

In many civil and military missions unmanned vehicles may be expected to cooperate with each other and act as a team. Two main aspects of the cooperation are addressed in this research – motion planning and task assignment, and the coupling between them. In our problem of interest Dubins and Reeds-Shepp dynamics are used to model aerial and ground vehicles’ kinematics, obstacles are assumed scattered in a 2D environment, and multiple targets need be serviced possibly with some priority. In the seminar an approach will first be presented that enables posing in an integrative manner and solving the two aspects associated with this problem of motion planning and task assignment. It is based on using relaxed Dubins and Reeds-Shepp paths (that do not enforce a final heading constraint) from each target to the next, thus making each path independent on the next task. Deterministic and stochastic search algorithms, for solving the motion planning problem, will be presented. For solving the task assignment problem, coupled with the motion planning one, two deterministic, heuristic and exhaustive, search algorithms will be presented. The results of sample runs and a Monte-Carlo simulations study will be presented and discussed.