Evolutionary Mission Planning

Abstract

The problem of mission planning enables a robot to solve for complex missions and thereafter execute the missions. The problem is seen as an advancement of the classical problem of motion planning wherein the task is to find a trajectory for a robot to go from a configuration A to a configuration B avoiding obstacles. The popular mechanism to solve the problem is using Temporal Logic specifications to specify a mission, and to thereafter use search strategies to solve the mission. The same requires an exponential complexity in terms of propositional variables to search and verify the mission plan. Further, optimality is usually not a criterion in finding a solution, and the transition costs are usually ignored leading to sub-optimal mission plans. As missions get more complex using a large number of propositional variables for specification, it may no longer be possible to use exponential complexity algorithms. The paper proposes the use of Evolutionary Computation to solve the same problem. We first develop a new restricted language for mission design. Even though the language is restrictive, it can specify a large number of missions of real life service robotics. Then we design an evolutionary computation framework to solve the mission. Probabilistic Roadmap technique is used to get the transition system and transition costs between regions of interest. The mission planner takes the mission specification and these transition costs to compute a mission plan. The mission plan is executed using a reactive navigator that can avoid any dynamic obstacle, other people and robots.