motion planning using lock-free concurrency. IEEE
Trans. Robotics 30, 5 (2014), 1123–1136.
18. Ichter, B., Harrison, J. and Pavone, M. Learning
sampling distributions for robot motion planning.
ICRA, 2018, 7087–7094.
19. Janson, L., Ichter, B., and Pavone, M. Deterministic
sampling-based motion planning: Optimality,
complexity, and performance. I. J. Robotics Res. 37, 1
20. Janson, L., Schmerling, E., Clark, A.A. and Pavone
M. Fast marching tree: A fast marching sampling-based method for optimal motion planning in many
dimensions. I. J. Robotics Res. 34, 7 (2015), 883–921.
21. Karaman, S. and Frazzoli, E. Sampling-based
algorithms for optimal motion planning. I. J. Robotics
Res. 30, 7 (2011), 846–894.
22. Kehoe, B., Patil, S., Abbeel, P., and Goldberg, K. A
survey of research on cloud robotics and automation.
IEEE Trans. Automation Science and Engineering 12, 2
23. Kleinbort, M., Salzman, O. and Halperin, D. Collision
detection or nearest-neighbor search? On the
computational bottleneck in sampling-based motion
planning. WAFR, 2016.
24. Kunz, T., Thomaz, A. and Christensen, H. Hierarchical
rejection sampling for informed kinodynamic planning
in high-dimensional spaces. ICRA, 2016, 89–96.
25. LaValle, S. M. Planning Algorithms. Cambridge
University Press, 2006.
26. LaValle, S.M. Motion planning: The essentials. IEEE
Robotics & Automation Mag. 18, 1 (2011), 79–89.
27. LaValle, S.M., Branicky, M.S. and Lindemann, S.R. On
the relationship between classical grid search and
probabilistic roadmaps. I. J. Robotics Res. 23, 7-8
28. Li, Y., Littlefield, Z. and Bekris, K.E. Asymptotically
optimal sampling-based kinodynamic planning. I. J.
Robotics Res. 35, 5 (2016), 528–564.
29. Lynch, K. M. and Park, F.C. Modern Robotics: Mechanics,
Planning, and Control. Cambridge University Press,
2017; http://hades.mech.northwestern.edu/ index.php/
30. Mandalika, A., Salzman, O. and Srinivasa, S.S. Lazy
receding horizon A* for efficient path planning in
graphs with expensive-to-evaluate edges. ICAPS,
31. Murray, S., Floyd-Jones, W., Qi, Y., Sorin, D.J. Konidaris,
G. Robot motion planning on a chip. RSS, 2016.
32. Plaku, E. and Kavraki, L.E. Quantitative analysis
of nearest-neighbors search in high-dimensional
sampling-based motion planning. WAFR, 2006, 3–18.
33. Salzman, O., Hemmer, M. and Halperin, D. On the
power of manifold samples in exploring configuration
spaces and the dimensionality of narrow passages.
IEEE Trans. Automation Science and Engineering 12, 2
34. Schulz, A., Wang, H., Grinspun, E., Solomon, J. and
Matusik, W. Interactive exploration of design trade-offs. ACM Trans. Graph. 37, 4 (2018), 131:1–131: 14.
35. Solovey, K. and Kleinbort, M. The critical radius in
sampling-based motion planning. RSS, 2018.
36. Solovey, K., Salzman, O. and Halperin, D. New
perspective on sampling-based motion planning via
random geometric graphs. I. J. Robotics Res. 37, 10
37. Stappen, A., Halperin, D. and Overmars, M.H. The
complexity of the free space for a robot moving amidst
fat obstacles. Computational Geometry 3, 6 (1993),
38. Vernaza, P. and Lee, D. D. Learning and exploiting low-dimensional structure for efficient holonomic motion
planning in high-dimensional spaces. I. J. Robotics
Res. 31, 14 (2012), 1739–1760.
39. Xie, C., van den Berg, J.P., Patil, S. and Abbeel, P.
Toward asymptotically optimal motion planning for
kinodynamic systems using a two-point boundary
value problem solver. ICRA, 2015, 4187–4194.
40. Zhou, B., Chiang, Y. and Yap, C. Soft subdivision motion
planning for complex planar robots. ESA, 2018,
Oren Salzman ( firstname.lastname@example.org) is an
assistant professor in the computer science department
at the Technion–Israel Institute of Technology.
© 2019 ACM 0001-0782/19/10 $15.00.
ning algorithms is looking at the problem from the hardware perspective.
Indeed, recent work suggested minimizing collision detection time by aggressively preprocessing a given scenario for a given robot. This required
designing robot-specific circuitry31 and
it is interesting to see if this approach
can be generalized to non-static environments. Another avenue where
hardware can be exploited is parallelization—motion-planning implementations tend to be highly sequential
and any advances in effective parallelization or amenability to highly parallel paradigms would also help the field
(also see Ichnowski and Alterovitz17
and references within). Finally, recent
advances in cloud-based computation could be highly beneficial and has
raised some initial attention from the
motion-planning community. 22
From the application point of view,
robots are leaving the cages of the industrial manufacturing production
lines and the safety of research labs, and
moving into the unstructured environments of everyday life. From human-in-the-way to human-in-the-loop, modern robotic problems typically involve
robot interactions with and around
humans. Solving such problems requires research in complementary
areas: algorithmic robotics, such as
motion planning and human-robot interaction, such as cognitive modeling,
intention recognition, and activity prediction. Accounting for humans in the
planning domain adds a multitude of
algorithmic constraints—from modeling human behavior to computing consistent, predictable, and safe paths.
However, they also allow for additional
Finally, as robots are being deployed, the robotics community is
collectively gathering experience
and data. Leveraging this experience
and data to improve the efficiency of
planning algorithms is an ongoing
challenge—from incorporating precomputed paths in roadmap-based
algorithms to applying advances in
machine learning to understand when
and how to apply existing tools, or to
develop new tools altogether.
One should not see learning as an
alternative to algorithmic, roadmap-
based planning, but as a complemen-
tary tool—organized search can act
as scaffolding for machine learning
algorithms. While machine learning
exploits correlations between similar
problem instances, search exploits
the structure within a problem. Thus,
the two are quite complementary.
Furthermore, machine learning algo-
rithms are typically data hungry and in
robotics there is often limited access
to huge amounts of real-world data.
For an overview of additional chal-
lenges and opportunities for robot
planning, see Alterovitz et al. 3
To truly impact our world, robot-planning capabilities must be enhanced. To do so, robotic researchers
need to harness tools from other communities and revisit existing, traditional algorithmic tools in order to make
them suitable for the unique, subtle
challenges that arise in this domain.
1. Adler, A., Berg, M., Halperin, D. and Solovey, K. Efficient
multi-robot motion planning for unlabeled discs in
simple polygons. IEEE Trans. Automation Science and
Engineering 12, 4 (2015), 1309–1317.
2. Aggar wal, C. C., Hinneburg, A. and Keim, D. A. On
the surprising behavior of distance metrics in high
dimensional space. In Proceedings of the Intern.
Conference on Database Theory. Springer, 2001,
3. Alterovitz, R., Koenig, S. and Likhachev, M. Robot
planning in the real world: Research challenges and
opportunities. AI Magazine 37, 2 (2016), 76–84.
4. Arslan, O. and Tsiotras, P. Use of relaxation methods
in sampling-based algorithms for optimal motion
planning. ICRA, 2013, 2421–2428.
5. Atariah, D. and Rote, G. Configuration space
visualization (video). SOCG, 2012 http://computational-geometry.org/SoCG- videos/socg12video/
6. Boeuf, A., Cortés, J., Alami, R. and Siméon, T.
Enhancing sampling-based kinodynamic motion
planning for quadrotors. IROS, 2015, 2447–2452.
7. Choudhury, S., Srinivasa, S. and Scherer, S. Bayesian
active edge evaluation on expensive graphs. IJCAI,
8. Dragan, A.D., Lee, K.C. T. and Srinivasa, S.S. Legibility
and predictability of robot motion. HRI, 2013,
9. Ekenna, C., Jacobs, S. A., Thomas, S. and Amato, N. M.
Adaptive neighbor connection for PRMs: A natural
fit for heterogeneous environments and parallelism.
IROS, 2013, 1249–1256.
10. Gammell, J.D., Barfoot, T.D., and Srinivasa, S.S.
Informed sampling for asymptotically optimal path
planning. IEEE Trans. Robotics 34, 4 (2018), 966–984.
11. Gammell, J.D., Srinivasa, S.S. and Barfoot, T.D. Batch
Informed Trees (BI T*): Sampling-based optimal
planning via the heuristically guided search of implicit
random geometric graphs. ICRA, 2015, 3067–3074.
12. Haghtalab, N., Mackenzie, S., Procaccia, A.D., Salzman,
O. and Srinivasa, S.S. The provable virtue of laziness in
motion planning. ICAPS, 2018, 106–113.
13. Halperin, D., Salzman, O. and Sharir, M. Algorithmic
motion planning. Handbook of Discrete and
Computational Geometry (3rd ed.), J.E. Goodman,
C. D. Toth, J. O’Rourke (Eds.). CRC Press, Inc., 2017,
14. Holladay, R.M., Salzman, O. and Srinivasa, S.S.
Minimizing task space Frechet error via efficient
incremental graph search. IEEE Robotics and
Automation Letters (2019). To appear.
15. Hsu, D., Latombe, J., and Kurniawati, H. On the
probabilistic foundations of probabilistic roadmap
planning. I. J. Robotics Res. 25, 7 (2006), 627–643.
16. Ichnowski, J. and Alterovitz, R. Fast nearest neighbor
search in SE( 3) for sampling-based motion planning.
WAFR, 2014, 197–214.
17. Ichnowski, J. and Alterovitz, R. Scalable multicore