Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published March 6, 2015 | Submitted
Report Open

Cross-entropy Temporal Logic Motion Planning

Abstract

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.

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.

Attached Files

Submitted - lwm-hscc-preprint.pdf

Files

lwm-hscc-preprint.pdf
Files (489.7 kB)
Name Size Download all
md5:e83d70683b60bf40d577e8d7c894c136
489.7 kB Preview Download

Additional details

Created:
August 22, 2023
Modified:
October 20, 2023