Evolutionary Planning for Multi-User Multi-Task Missions

摘要

The problem of mission planning is to enable robots solve complex missions with Boolean and temporal operators in the mission specification. Typically, missions are specified using a Linear Temporal Logic Formulation and solved by using a model verification approach which has an exponential complexity. Given a language which is polynomial verifiable, evolutionary paradigm of mission planning can enable probabilistic optimality and probabilistic completeness, thus enabling the use of solvers for a very high number of variables, which is impossible to do using the model verification techniques. This paper motivates the heuristic of a mission consisting of a number of tasks, such that each task is a complex instruction given by a user, while many such users share a robot. The heuristic is used to generate a near-optimal solution of tasks that can then be fused optimally by a Dynamic Programming approach to make the solution of the mission. However, the problem is not decomposable and optimal solutions of tasks do not result in an optimal solution to mission. Hence a 2step algorithm is used. The first step computes a near-optimal solution of the tasks. The second step does a full Genetic Algorithm search to generate task solutions that eventually fused by a Dynamic Programming approach produce an optimal mission solution. Comparative analysis is done with numerous baselines and the proposed approach is experimentally shown to perform better than all baselines. The experiments are also done on the Pioneer LX robot using the Robot Operating System framework.