Optimal path planning under temporal logic constraints

In this paper we present a method for automatically generating optimal robot trajectories satisfying high level mission specifications. The motion of the robot in the environment is modeled as a weighted transition system. The mission is specified by a general linear temporal logic formula. In addition, we require that an optimizing proposition must be repeatedly satisfied. The cost function that we seek to minimize is the maximum time between satisfying instances of the optimizing proposition. For every environment model, and for every formula, our method computes a robot trajectory which minimizes the cost function. The problem is motivated by robotic monitoring and data gathering. In this setting, the optimizing proposition is satisfied at locations where data can be uploaded, and the formula specifies a an infinite horizon data collection mission. Our method utilizes Büchi automata to produce an automaton (which can be thought of as a graph) whose runs satisfy the temporal logic formula. We then present a graph algorithm which computes a path corresponding to the optimal robot trajectory. We also present an implementation for a robot performing a data gathering mission.

Authors

• Stephen L. Smith 0001
• Jana Tumova
• Calin Belta
• Daniela Rus

Keywords

• Automata
• Cost function
• Roads
• Trajectory
• Vehicles
• Steady-state
• Temporal Constraints
• Temporal Logic
• Temporal Logic Constraints
• Maximum Time
• Transit System
• Trajectory Optimization
• Robot Motion
• Graph Algorithms
• Robot Trajectory
• Robots In Environments
• Linear Logic
• Infinity
• Travel Time
• Shortest Path
• Time Sequence
• Time Instants
• Desktop Computer
• Mixed Integer Linear Programming
• Starting State
• Minimum Cost Function
• Temporal Operators
• Motion Primitives
• Model Checking
• Dijkstra’s Algorithm
• Pair Of Vertices
• Optimization Run
• Vehicle Routing
• Data Upload