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
Name | Size | Download all |
---|---|---|
md5:e83d70683b60bf40d577e8d7c894c136
|
489.7 kB | Preview Download |
Additional details
- Eprint ID
- 55595
- Resolver ID
- CaltechCDSTR:2015.002
- United Technologies Corporation
- IBM Corp.
- National Defense Science and Engineering Graduate (NDSEG) Fellowship
- Boeing Corporation
- Created
-
2015-03-06Created from EPrint's datestamp field
- Updated
-
2021-11-10Created from EPrint's last_modified field
- Caltech groups
- Control and Dynamical Systems Technical Reports