A Caltech Library Service

Cross-entropy Temporal Logic Motion Planning

Livingston, Scott C. and Wolff, Eric M. and Murray, Richard M. (2015) Cross-entropy Temporal Logic Motion Planning. California Institute of Technology , Pasadena, CA. (Unpublished)

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


This paper presents a method for optimal trajectory generation for discrete-time nonlinear systems with linear temporal logic (LTL) task specifications. Our approach is based on recent advances in stochastic optimization algorithms for optimal trajectory generation. These methods rely on estimation of the rare event of sampling optimal trajectories, which is achieved by incrementally improving a sampling distribution so as to minimize the cross-entropy. A key component of these stochastic optimization algorithms is determining whether or not a trajectory is collision-free. We generalize this collision checking to efficiently verify whether or not a trajectory satisfies a LTL formula. Interestingly, this verification can be done in time polynomial in the length of the LTL formula and the trajectory. We also propose a method for efficiently re-using parts of trajectories that only partially satisfy the specification, instead of simply discarding the entire sample. Our approach is demonstrated through numerical experiments involving Dubins car and a generic point-mass model subject to complex temporal logic task specifications.

Item Type:Report or Paper (Technical Report)
Related URLs:
URLURL TypeDescription
Murray, Richard M.0000-0002-5785-7481
Contact Email
Additional Information:The authors thank Marin Kobilarov for providing source code implementing the CE method in MATLAB. This work was partially supported by United Technologies Corporation and IBM, through the industrial cyberphysical systems (iCyPhy) consortium. The second author was partially supported by an NDSEG fellowship and the Boeing Corporation while at Caltech.
Group:Control and Dynamical Systems Technical Reports
Funding AgencyGrant Number
United Technologies CorporationUNSPECIFIED
National Defense Science and Engineering Graduate (NDSEG) FellowshipUNSPECIFIED
Boeing CorporationUNSPECIFIED
Subject Keywords:motion planning; stochastic optimization; cross-entropy; linear temporal logic; incremental synthesis
Record Number:CaltechCDSTR:2015.002
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:55595
Deposited By: Scott Livingston
Deposited On:06 Mar 2015 22:47
Last Modified:10 Nov 2021 20:47

Repository Staff Only: item control page