Abstract
Recent progress in sampling-based planning has provided performance guarantees in terms of optimizing trajectory cost even in the presence of significant dynamics. The STABLE_SPARSE_RRT (SST) algorithm has these desirable path quality properties and achieves computational efficiency by maintaining a sparse set of state-space samples. The current paper focuses on field robotics, where workspace information can be used to effectively guide the search process of a planner. In particular, the computational performance of SST is improved by utilizing appropriate heuristics. The workspace information guides the exploration process of the planner and focuses it on the useful subset of the state space. The resulting Informed- SST is evaluated in scenarios involving either ground vehicles or quadrotors. This includes testing for a physically-simulated vehicle over uneven terrain, which is a computationally expensive planning problem.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Ai-Omari, M.A.R., Jaradat, M.A., Jarrah, M.: Integrated simulation platform for indoor quadrotor applications. In: 2013 9th International Symposium on Mechatronics and its Applications (ISMA) (2013)
Bekris, K., Kavraki, L.: Informed and probabilistically complete search for motion planning under differential constraints. In: First International Symposium on Search Techniques in Artificial Intelligence and Robotics (STAIR), Chicago, IL (2008)
Choudhury, S., Gammell, J.D., Barfoot, T.D., Srinivasa, S.S., Scherer, S.: Regionally accelerated batch informed trees (rabit*): A framework to integrate local information into optimal path planning. In: 2016 IEEE International Conference on Robotics and Automation (ICRA), pp. 4207–4214. IEEE (2016)
Clement, L., Kelly, J., Barfoot, T.D.: Monocular visual teach and repeat aided by local ground planarity. In: Field and Service Robotics, pp. 547–561. Springer (2016)
Cohen, B.J., Chitta, S., Likhachev, M.: Search-based planning for manipulation with motion primitives. In: 2010 IEEE International Conference on Robotics and Automation (ICRA), pp. 2902–2908. IEEE (2010)
Coumans, E.: Bullet Physics Engine. http://bulletphysics.org (2012)
Diankov, R., Kuffner, J.: Randomized statistical path planning. In: IEEE/RSJ International Conference on Intelligent Robots and Systems, 2007. IROS 2007, pp. 1–6. IEEE (2007)
Fang, Z., Yang, S., Jain, S., Dubey, G., Roth, S., Maeta, S., Nuske, S., Zhang, Y., Scherer, S.: Robust autonomous flight in constrained and visually degraded shipboard environments. J. Field Robot. 34(1), 25–52 (2017)
Ferguson, D., Howard, T.M., Likhachev, M.: Motion planning in urban environments: Part II. In: IEEE/RSJ International Conference on Intelligent Robots and Systems, 2008. IROS 2008, pp. 1070–1076. IEEE (2008)
Ferguson, D., Stentz, A.: Using interpolation to improve path planning: the field d* algorithm. J. Field Robot. 23(2), 79–101 (2006)
Gammell, J.D., Srinivasa, S.S., Barfoot, T.D.: Informed rrt*: optimal sampling-based path planning focused via direct sampling of an admissible ellipsoidal heuristic. arXiv:1404.2334 (2014)
Hollinger, G.A., Sukhatme, G.S.: Sampling-based robotic information gathering algorithms. Int. J. Robot. Res. 33(9), 1271–1287 (2014)
Inotsume, H., Creager, C., Wettergreen, D., Whittaker, W.R.L.: Finding routes for efficient and successful slope ascent for exploration rovers. In: The International Symposium on Artificial Intelligence, Robotics and Automation in Space (i-SAIRAS) 2016 (2016)
Islam, F., Narayanan, V., Likhachev, M.: Dynamic multi-heuristic A. In: 2015 IEEE International Conference on Robotics and Automation (ICRA), pp. 2376–2382. IEEE (2015)
Kalisiak, M., van de Panne, M.: RRT-blossom: RRT with a local flood-fill behavior. In: Proceedings 2006 IEEE International Conference on Robotics and Automation, 2006. ICRA 2006, pp. 1237–1242. IEEE (2006)
Karaman, S., Frazzoli, E.: Sampling-based algorithms for optimal motion planning. Int. J. Robot. Res. 30(7), 846–894 (2011)
Kavraki, L.E., Svestka, P., Latombe, J.C., Overmars, M.H.: Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Trans. Robot. Autom. 12(4), 566–580 (1996)
Kunz, T., Stilman, M.: Kinodynamic RRTs with fixed time step and best-input extension are not probabilistically complete. In: Algorithmic Foundations of Robotics XI, pp. 233–244. Springer (2015)
LaValle, S., Kuffner, J.: Randomized kinodynamic planning. IJRR 20(5), 378–400 (2001)
Li, Y., Littlefield, Z., Bekris, K.E.: Sparse methods for efficient asymptotically optimal kinodynamic planning. In: Workshop on Algorithmic Foundations of Robotics (WAFR) (2014)
Li, Y., Littlefield, Z., Bekris, K.E.: Asymptotically optimal sampling-based kinodynamic planning. Int. J. Robot. Res. 35(5), 528–564 (2016)
Likhachev, M., Ferguson, D.: Planning long dynamically-feasible maneuvers for autonomous vehicles. Int. J. Robot. Res. (IJRR) 28, 933–945 (2009)
Likhachev, M., Stentz, A.: R* search. In: Proceedings of the National Conference on Artificial Intelligence (AAAI). Citeseer (2008)
Littlefield, Z., Klimenko, D., Kurniawati, H., Bekris, K.E.: The importance of a suitable distance function in belief-space planning. In: International Symposium on Robotic Research (ISRR) (2015)
Nash, A., Daniel, K., Koenig, S., Felner, A.: Theta*: any-angle path planning on grids. In: AAAI, pp. 1177–1183 (2007)
Pereira, A.A., Binney, J., Hollinger, G.A., Sukhatme, G.S.: Risk-aware path planning for autonomous underwater vehicles using predictive ocean models. J. Field Robot. 30(5), 741–762 (2013)
Persson, S.M., Sharf, I.: Sampling-based A* algorithm for robot path-planning. Int. J. Robot. Res. 33(13), 1683–1708 (2014)
Pivtoraiko, M., Kelly, A.: Kinodynamic motion planning with state lattice motion primitives. In: 2011 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 2172–2179. IEEE (2011)
Pivtoraiko, M., Knepper, R.A., Kelly, A.: Differentially constrained mobile robot motion planning in state lattices. J. Field Robot. 26(3), 308–333 (2009)
Posa, M., Kuindersma, S., Tedrake, R.: Optimization and stabilization of trajectories for constrained dynamical systems. In: 2016 IEEE International Conference on Robotics and Automation (ICRA), pp. 1366–1373. IEEE (2016)
Wells, A., Plaku, E.: Adaptive sampling-based motion planning for mobile robots with differential constraints. In: Conference Towards Autonomous Robotic Systems, pp. 283–295. Springer (2015)
Ziegler, J., Stiller, C.: Spatiotemporal state lattices for fast trajectory planning in dynamic on-road driving scenarios. In: IEEE/RSJ International Conference on Intelligent Robots and Systems, 2009. IROS 2009, pp. 1879–1884. IEEE (2009)
Zucker, M., Ratliff, N., Dragan, A.D., Pivtoraiko, M., Klingensmith, M., Dellin, C.M., Bagnell, J.A., Srinivasa, S.S.: CHOMP: covariant Hamiltonian optimization for motion planning. Int. J. Robot. Res. 32(9–10), 1164–1193 (2013)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer International Publishing AG
About this paper
Cite this paper
Littlefield, Z., Bekris, K.E. (2018). Informed Asymptotically Near-Optimal Planning for Field Robots with Dynamics. In: Hutter, M., Siegwart, R. (eds) Field and Service Robotics. Springer Proceedings in Advanced Robotics, vol 5. Springer, Cham. https://doi.org/10.1007/978-3-319-67361-5_29
Download citation
DOI: https://doi.org/10.1007/978-3-319-67361-5_29
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-67360-8
Online ISBN: 978-3-319-67361-5
eBook Packages: EngineeringEngineering (R0)