This paper is concerned with motion planning for non-linear robotic systems operating in constrained environments. A method for computing high-quality trajectories is proposed building upon recent developments in sampling-based motion planning and stochastic optimization. The idea is to equip sampling-based methods with a probabilistic model that serves as a sampling distribution and to incrementally update the model during planning using data collected by the algorithm. At the core of the approach lies the cross-entropy method for the estimation of rare-event probabilities. The cross-entropy method is combined with recent optimal motion planning methods such as the rapidly exploring random trees (RRT*) in order to handle complex environments. The main goal is to provide a framework for consistent adaptive sampling that correlates the spatial structure of trajectories and their computed costs in order to improve the performance of existing planning methods.
BotevZKroeseDP (2004) Global likelihood optimization via the cross-entropy method with an application to mixture models. In Winter Simulation Conference, pp. 529–535.
3.
BurnsBBrockO (2005a) Sampling-based motion planning using predictive models. In IEEE International Conference on Robotics and Automation, April 2005, pp. 3120–3125.
4.
BurnsBBrockO (2005b) Toward optimal configuration space sampling. In Robotics: Science and Systems.
5.
ChirikjianGS (2012) Applied and numerical harmonic analysis. Stochastic Models, Information Theory, and Lie Groups. Volume II: Analytic Methods and Modern Applications. Basel: Birkhäuser.
6.
ChosetHLynchKMHutchinsonSKantorGABurgardWKavrakiLE. (2005) Principles of Robot Motion: Theory, Algorithms, and Implementations. Cambridge, MA: MIT Press.
7.
ClarkeFHLedyaevYSSternRJWolenskiPR (1998) Nonsmooth Analysis and Control Theory. Berlin: Springer.
8.
CostaAJonesODKroeseD (2007) Convergence properties of the cross-entropy method for discrete optimization. Operations Research Letters35: 573–580.
9.
De BonetJSIsbellCLJrViolaPA (1996) Mimic: Finding optima by estimating probability densities. In Proceedings of NIPS’96, pp. 424–430.
10.
DennyJAmatoNM (2011) Toggle PRM: Simultaneous mapping of C-free and C-obstacle - a study in 2D. In Proceedings IEEE IROS2011, pp. 2632–2639.
11.
FigueiredoMAFJainAK (2002) Unsupervised learning of finite mixture models. IEEE Transactions on Pattern Analysis and Machine Intelligence24: 381–396.
12.
FrazzoliEDahlehMAFeronE (2005) Maneuver-based motion planning for nonlinear systems with symmetries. IEEE Transactions on Robotics21: 1077–1091.
13.
Homem-de MelloT (2007) A study on the cross-entropy method for rare-event probability estimation. INFORMS Journal on Computing19: 381–394.
14.
HsuDLatombeJ-CKurniawatiH (2006) On the probabilistic foundations of probabilistic roadmap planning. The International Journal of Robotics Research25: 627–643.
15.
HsuDSanchez-AnteGSunZ (2005) Hybrid PRM sampling with a cost-sensitive adaptive strategy. In Proceedings IEEE International Conference on Robotics and Automation (ICRA 2005), pp. 3874–3880.
16.
HuJFuMCMarcusSI (2007) A model reference adaptive search method for global optimization. Operations Research55: 549–568.
17.
HuJHuP (2009) On the performance of the cross-entropy method. In Winter Simulation Conference (WSC ’09), pp. 459–468.
18.
IgelCSuttorpTHansenN (2006) A computational efficient covariance matrix update and a (1+1)-CMA for evolution strategies. In Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation GECCO. New York: ACM Press, pp. 453–460.
19.
KalakrishnanMChittaSTheodorouEPastorPSchaalS (2011) STOMP: stochastic trajectory optimization for motion planning. In IEEE International Conference on Robotics and Automation (ICRA).
20.
KalisiakMvandePanneM (2007) Faster motion planning using learned local viability models. In Proceedings IEEE International Conference on Robotics and Automation (ICRA’07), pp. 2700–2705.
21.
KaramanSFrazzoliE (2010) Optimal kinodynamic motion planning using incremental sampling-based methods. In IEEE Conference on Decision and Control (CDC), Atlanta, GA, December 2010.
22.
KaramanSFrazzoliE (2011) Sampling-based algorithms for optimal motion planning. International Journal of Robotics Research (to appear), 2011.
23.
KaramanSWalterMRPerezAFrazzoliETellerS.Anytime motion planning using the RRT*. In IEEE Conference on Robotics and Automation (ICRA), April 2011.
24.
KnepperRAMasonMT (2011) Realtime informed path sampling for motion planning search. In 15th International Symposium on Robotics Research (ISRR).
25.
KnepperRASrinivasaSMasonMT (2010) An equivalence relation for local path sets. In LatombeJ-CHsuDIslerVLinMC (eds), The Ninth International Workshop on the Algorithmic Foundations of Robotics. Heidelberg: Springer.
26.
KobilarovM (2011) Cross-entropy randomized motion planning. In Proceedings of Robotics: Science and Systems, Los Angeles, CA, June 2011.
27.
KroeseDPorotskySRubinsteinR (2006) The cross-entropy method for continuous multi-extremal optimization. Methodology and Computing in Applied Probability8: 383–407.
28.
KurniawatiHHsuD (2004) Workspace importance sampling for probabilistic roadmap planning. In Proceedings IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2004), vol. 2, pp. 1618–1623.
29.
LaddAMKavrakiLE (2005) Fast Tree-Based Exploration of State Space for Robots with Dynamics. Berlin: Springer, pp. 297–312.
30.
LarrañagaPLozanoJA (eds) (2002) Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation. Dordrecht: Kluwer Academic Publishers.
31.
LaValleSM (2006) Planning Algorithms. Cambridge: Cambridge University Press.
32.
LiYBekrisKE (2010) Balancing state-space coverage in planning with dynamics. In Proceedings IEEE International Conference on Robotics and Automation (ICRA), pp. 3246–3253.
33.
MargolinL (2005) On the convergence of the cross-entropy method. Annals of Operations Research134: 201–214.
34.
McLachlanGPeelD (2002) Finite Mixture Models. New York: John Wiley & Sons, Inc.
35.
MooreASchneiderJ (1995) Memory-based stochastic optimization. In Neural Information Processing Systems 8.
36.
MurrayRMRathinamMSluisWM (1995) Differential flatness of mechanical control systems. In Proceedings ASME International Congress and Exposition.
37.
MurrayRMSastryS (1993) Nonholonomic motion planning: Steering using sinusoids. IEEE Transactions on Automatic Control38: 700–716.
38.
PelikanMGoldbergDELoboFG (2002) A survey of optimization by building and using probabilistic models. Computational Optimization and Applications21: 5–20.
39.
PowellWB (2007) Approximate Dynamic Programming: Solving the Curses of Dimensionality ( Wiley Series in Probability and Statistics). New York: John Wiley & Sons, Inc.
40.
RasmussenCEWilliamsCKI (2005) Gaussian Processes for Machine Learning (Adaptive Computation and Machine Learning). Cambridge, MA: The MIT Press.
41.
RatliffNZuckerMBagnellJASrinivasaS (2009) Chomp: Gradient optimization techniques for efficient motion planning. In Proceedings IEEE International Conference on Robotics and Automation (ICRA’09), pp. 489–494.
42.
RickertMBrockOKnollA (2008) Balancing exploration and exploitation in motion planning. In Proceedings IEEE International Conference on Robotics and Automation (ICRA 2008), pp. 2812–2817.
43.
RubinsteinRYKroeseDP (2004) The Cross-entropy Method: A Unified Approach to Combinatorial Optimization. New York: Springer.
44.
RubensteinRYKroeseDP (2008) Simulation and the Monte Carlo Method. New york: John Wiley & Sons, Inc.
45.
SeegerM (2003) Pac–Bayesian generalisation error bounds for Gaussian process classification. Journal of Machine Learning Research3: 233–269.
46.
SpallJC (2003) Introduction to Stochastic Search and Optimization. New York: John Wiley & Sons, Inc..
47.
TheodorouEBuchliJSchaalS (2010) A generalized path integral control approach to reinforcement learning. Journal of Machine Learning Research11: 3137–3181.
48.
YershovDLaValleS (2011) Sufficient conditions for the existence of resolution complete planning algorithms. In HsuDIslerVLatombeJ-CLinM (eds), Algorithmic Foundations of Robotics IX (Springer Tracts in Advanced Robotics, vol. 68). Berlin: Springer, pp. 303–320.
49.
ZhigljavskyAZilinskasA (2008) Stochastic Global Optimization. New York: Springer.
50.
ZuckerMKuffnerJBagnellJA (2008) Adaptive workspace biasing for sampling-based planners. In Proceedings IEEE International Conference on Robotics and Automation (ICRA’08), pp. 3757–3762.
