Cross-Entropy Motion Planning. Kobilarov. International Journal of Robotics Research. 2012.


  1. Not the same research as presented in https://aresearch.wordpress.com/2012/11/05/cross-entropy-randomized-motion-planning-marin-kobilarov-rss-07/
  2. This approach is for the noiseless setting
  3. The previous paper deals with using cross-entropy directly, while this paper discusses a combination of cross-entropy and RRT*
  4. The additional RRT* component is intended to help deal with the more difficult regions of planning “In particular, more complicated obstacles such as those associated with narrow passages significantly shrink the feasible regiouns in trajectory space and thus, in the abscence of a good prior, can render the method intractable due to the large number of rejected samples.”
  5. Considers open-loop planning, although mentions there are a two ways to parameterize trajectories:
    1. As a sequence of actions: “Conditions for resolution completeness of planning with such primitives [encoding of sequence of actions with time duration for each action] have been established (Yershov and LaValle 2011).
    2. As a sequence of states
    3. The paper outlines methods for doing both, as either may be better depending on the domain
  6. “In general, the problem cannot be solved in closed form since both the dynamics and constraints can be non-linear.  Gradient-based optimization is not suitable unless a good starting guess is chosen since the constraints impose many local minima.  In addition, constraints corresponding to arbitrary obstacles can be non-smooth and require special differentiation (Clarke et al. 1998) to guarantee convergence.”
  7. In sampling based motion planning, a graph is produced that is a finite approximation to the infinite set of feasible trajectories, so the original problem can be solved approximately through the graph
  8. Care about optimality at the limit.  PRMs approach optimality, but this occurs at an exponentially slow rate (defined how excatly?) due to the increasing number of edges+vertices “which in higher dimensions becomes computationally intractable.”
    1. So this paper cares about RRTs and not PRMs
  9. RRT* has a problem of uniformly distributing samples, and most of these samples don’t help at all.  By using cross-entropy optimization on top, it attempts to allocate samples along the path where the optimal trajectory may lie
    1. CE optimizes the method of sampling vertices
    2. RRT* is further optimized to always attempt to connect newly added nodes to the goal
  10. “Even though general theoretical convergence of the CE method has been shown [citations] actual rates of convergence, sample complexity, or precise performance guarantees remain open problems.”
  11. The difference between RRT* and cross-ent is that one samples in state space, the other in parameterized trajectories (such as action sequences)
  12. CE was originally designed for rare-event estimation. “The rare event of interest in this work is finding a parameter Z with a real-valued cost J(Z) which happens to be very close to the cost of an optimal parameter Z*… the rare-event estimation is equivalent to the global optimization of J(Z)”
  13. Uses Gaussain Mixture Models as the basis for CE optimizaiton, because it is easy to do with EM
    1. Although it can only capture as many local regions as components in the mixture, each Gaussian component can be regarded as an approximation of a local second-order model of the objective function centered at each mean (by considering the covariance as the inverse Hessian of the cost – I would like a citation/further discussion of this)
  14. Discusses connection to CE and CMA as well as another algorithm called EDA.  The connection to CMA was already discussed before in the CMA-ES paper.  Says the two are virtually identical in the Gaussian case.
  15. “In case when very few elite samples are available a classical GMM EM algorithm will fail to estimate correct means and covariances.”  So they add additional noise, as is common in Cross-Ent
  16. Gives examples of double integrator(actually in 2D, with obstacles), driving (dubins?),  and helicopter navigation
  17. In the helicopter domain, 85% of rollouts with regular CE are thrown out, so RRT* is added to make samples more useful
  18. In TCE RRT* (There is also an SCE proposed), examines correlations of states across entire trajectories
  19. In the helicopter, shows expected optimal trajectory as a result of 3 mixture components (I’m not sure what dimension, though).  The result is very complex in terms of the resulting path in the x,y space.
  20. Discusses other distributions that may make a good tradeoff between efficiency and accuracy.
  21. In a higher dimensional double-integrator domain with obstacles, the two algs here SCE-RRT*, and TCE-RRT* outperform RRT*.
  22. Use domain I havent heard of which is a weird version of a plane that has dubins steering in x,y and double integrator in z.
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: