Complex mission optimization for Multiple-UAVs using Linear Temporal Logic

This paper discusses a class of mission planning problems in which mission objectives and relative timing constraints are specified using the linear temporal logic language LTL
_-x
. Among all mission plans that satisfy the LTL
_-x
specifications, it is desired to find those minimizing a given cost functional. We show that such an optimization problem can be formulated as a mixed-integer linear program, and present an algorithm for this purpose. This algorithm mainly relies on a novel systematic procedure which converts a given LTL
_-x
formula into a set of mixed-integer linear constraints. The approach presented here can be used for multiple-UAV mission planning purposes, allowing the operator to specify complex mission objectives in LTL
_-x
in a very natural manner; the proposed algorithm constructs the optimal mission plan satisfying the given LTL
_-x
specification. Examples for practical problem sizes are presented and discussed in the paper.