Simultaneous planning of sampling and optimization: study on lazy evaluation and configuration free space approximation for optimal motion planning algorithm

• Bialkowski, J., Karaman, S., & Frazzoli, E. (2011). Massively parallelizing the RRT and the RRT. In IEEE/RSJ international conference on intelligent robots and systems (IROS) (pp 3513–3518).

• Bialkowski, J., Karaman, S., Otte, M., & Frazzoli, E. (2013). Efficient collision checking in sampling-based motion planning. In International workshop on the algorithmic foundations of robotics (WAFR) (pp. 365–380).

• Bialkowski, J., Otte, M., & Frazzoli, E. (2013). Free-configuration biased sampling for motion planning. In IEEE/RSJ international conference on intelligent robots and systems (IROS) (pp 1272–1279).

• Burns, B., & Brock, O. (2005a). Sampling-based motion planning using predictive models. In IEEE International conference on robotics and automation (ICRA) (pp. 3120–3125).

• Burns, B., & Brock, O. (2005b). Toward optimal configuration space sampling. Cambridge: RSS.

  Book  Google Scholar 

• Choudhury, S., Gammell, J. D., Barfoot, T. D., Srinivasa, S. S., & Scherer, S. (2016). Regionally accelerated batch informed trees (\({{\rm RABIT}}^{*}\)): A framework to integrate local information into optimal path planning. In IEEE international conference on robotics and automation (ICRA) (pp. 4207–4214).

• Deheuvels, P. (1983). Strong bounds for multidimensional spacings. Probability Theory and Related Fields, 64(4), 411–424.

  MathSciNet  MATH  Google Scholar 

• Denny, J., & Amato, N. M. (2011). Toggle PRM: Simultaneous mapping of C-free and C-obstacle—A study in 2D. In IEEE/RSJ International conference on intelligent robots and systems (IROS) (pp 2632–2639).

• Denny, J., & Amato, N. M. (2012). The toggle local planner for sampling-based motion planning. In IEEE International conference on robotics and automation (ICRA) (pp. 1779–1786).

• Denny, J., Shi, K., & Amato, N. M. (2013). Lazy toggle PRM: A single-query approach to motion planning. In 2013 IEEE international conference on robotics and automation (ICRA) (pp 2407–2414). IEEE.

• Frigioni, D., Marchetti-Spaccamela, A., & Nanni, U. (2000). Fully dynamic algorithms for maintaining shortest paths trees. Journal of Algorithms, 34(2), 251–281.

  Article  MathSciNet  Google Scholar 

• Gammell, J. D., Srinivasa, S. S., & Barfoot, T. D. (2014). Informed \({{\rm RRT}}^*\): Optimal sampling-based path planning focused via direct sampling of an admissible ellipsoidal heuristic. In IEEE/RSJ international conference on intelligent robots and systems (IROS) (pp 2997–3004).

• Gammell, J. D., Srinivasa, S. S., & Barfoot, T. D. (2015). Batch informed trees (\({{\rm BIT}}^{*}\)): Sampling-based optimal planning via the heuristically guided search of implicit random geometric graphs. In IEEE international conference on robotics and automation (ICRA) (pp 3067–3074).

• Haghtalab, N., Mackenzie, S., Procaccia, A. D., Salzman, O., & Srinivasa, S. S. (2018). The provable virtue of laziness in motion planning. In International conference on automated planning and scheduling.

• Hauser, K. (2015). Lazy collision checking in asymptotically-optimal motion planning. In IEEE international conference on robotics and automation (ICRA).

• Jaromczyk, J. W., & Toussaint, G. T. (1992). Relative neighborhood graphs and their relatives. Proceedings of the IEEE, 80(9), 1502–1517.

  Article  Google Scholar 

• Jeon, J. H., Karaman, S., & Frazzoli, E. (2011). Anytime computation of time-optimal off-road vehicle maneuvers using the \({{\rm RRT}}^{*}\). In IEEE conference on decision and control and European control conference (CDC-ECC) (pp 3276–3282).

• Kalakrishnan, M., Chitta, S., Theodorou, E., Pastor, P., & Schaal, S. (2011). STOMP: Stochastic trajectory optimization for motion planning. In IEEE international conference on robotics and automation (ICRA) (pp 4569–4574).

• Karaman, S., & Frazzoli, E. (2010). Incremental sampling-based algorithms for optimal motion planning. arXiv preprint arXiv:1005.0416.

• Karaman, S., & Frazzoli, E. (2011). Sampling-based algorithms for optimal motion planning. International Journal of Robotics Research (IJRR), 30(7), 846–894.

  Article  Google Scholar 

• Karaman, S., Walter, M., Perez, A., Frazzoli, E., & Teller, S. (2011). Anytime motion planning using the \({{\rm RRT}}^{*}\). In IEEE international conference on robotics and automation (ICRA) (pp 1478–1483).

• Kavraki, L. E., Svestka, P., Latombe, J.-C., & Overmars, M. H. (1996). Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Transactions on Robotics and Automation, 12(4), 566–580.

  Article  Google Scholar 

• Kim, D., Kwon, Y., & Yoon, S. (2018a). Adaptive lazy collision checking for optimal sampling-based motion planning. In International conference on ubiquitous robots (pp. 2519–2526).

• Kim, D., Kwon, Y., & Yoon, S. (2018b). Dancing \({{\rm PRM}}^*\) : Simultaneous planning of sampling and optimization with configuration free space approximation. In IEEE international conference on robotics and automation (ICRA) (pp. 2519–2526). IEEE.

• Kleinbort, M., Salzman, O., & Halperin, D. (2016). Collision detection or nearest-neighbor search? On the computational bottleneck in sampling-based motion planning. In International workshop on the algorithmic foundations of robotics (WAFR).

• Koenig, S., Likhachev, M., & Furcy, D. (2004). Lifelong planning \({{\rm A}}^*\). Artificial Intelligence, 155(1–2), 93–146.

  Article  MathSciNet  Google Scholar 

• Kuntz, A., Bowen, C., & Alterovitz, R. (2017). Fast anytime motion planning in point clouds by interleaving sampling and interior point optimization. In Proceedings of the international symposium on robotics research (ISRR) (pp. 1–16).

• LaValle, S. M. (1998). Rapidly-exploring random trees: A new tool for path planning. Technical Report 98-11, Iowa State University.

• LaValle, S. M. (2006). Planning algorithms. Cambridge: Cambridge University Press.

  Book  Google Scholar 

• Lindemann, S. R., & LaValle, S. M. (2005). Current issues in sampling-based motion planning. In Robotics research. The eleventh international symposium (pp. 36–54). Springer.

• Niederreiter, H. (1992). Random number generation and quasi-Monte Carlo methods (Vol. 63). Philadelphia: SIAM.

  Book  Google Scholar 

• Otte, M., & Frazzoli, E. (2015). RRT-X: Real-time motion planning/replanning for environments with unpredictable obstacles. In Algorithmic Foundations of Robotics XI (pp. 461–478). Springer.

• Pan, J., & Manocha, D. (2016). Fast probabilistic collision checking for sampling-based motion planning using locality-sensitive hashing. International Journal of Robotics Research (IJRR), 35(12), 1477–1496.

  Article  Google Scholar 

• Park, C., Pan, J., & Manocha, D. (2012). ITOMP: Incremental trajectory optimization for real-time replanning in dynamic environments. In International conference on automated planning and scheduling.

• Rickert, M., Sieverling, A., & Brock, O. (2014). Balancing exploration and exploitation in sampling-based motion planning. IEEE Transactions on Robotics (T-RO), 30(6), 1305–1317.

• Rohmer, E., Freese, M., & Singh, S. P. N. (2013). V-REP: A versatile and scalable robot simulation framework. In IEEE/RSJ international conference on intelligent robots and systems (IROS).

• Shkolnik, A., & Tedrake, R. (2011). Sample-based planning with volumes in configuration space. arXiv preprint arXiv:1109.3145.

• Sucan, I. A., Moll, M., & Kavraki, L. E. (2012). The open motion planning library. IEEE Robotics & Automation Magazine, 19(4), 72–82.

  Article  Google Scholar 

• Zucker, M., Ratliff, N., Dragan, A. D., Pivtoraiko, M., Klingensmith, M., Dellin, C. M., et al. (2013). CHOMP: Covariant Hamiltonian optimization for motion planning. International Journal of Robotics Research (IJRR), 32(9–10), 1164–1193.

  Article  Google Scholar 

Download references