Analytic Optimal-Based Time Horizon Using Pontryagin's Maximum Principle for Spatial Navigation

Oren Gal

Abstract


This paper addresses the issue of agent motion planning for spatial applications using an analytic optimal time horizon solution as basic character of our search. Specifically, we propose the analytic optimal time horizon concept as a leading feature for our local on-line planner for omni-directional robots using Velocity Obstacle (VO). For the first time, we propose a solution to the basic limitation of the VO search and planning method, i.e. when all the dynamic available velocities for the next time step are blocked inside the velocity space and there is no legal node at the next time step of the greedy search using classic VO concept. In this paper, we present unified computation of the minimum time horizon which is formulated as a minimum time problem for omni-directional models. The analytic solution describes minimal and safe VO and allows efficient on-line planning in dynamic and static environments searching safe nodes. At each time step, a local greedy search in velocity space is explored. The analytic solution defines VO shape and by that set the bounded velocity space and the next optimal node outside VO explored in the next time step. We introduce on-line planner for omni-directional robot that generates near-time optimal trajectories to the goal by using optimal time horizon. We demonstrate the solution of our approach in simulations showing the efficiency relative to the traditional VO for on-line motion planning that can be extended for spatial applications in urban scenes

Keywords


Collision Avoidance; Motion Planning; Spatial Applications

Full Text:

PDF

References


J.-C. Latombe, Robot Motion Planning. Kluwer Academic Publishers, 1990.

M. Erdman and T. Lozano-Perez, “On multiple moving objects,” Algorithmica, vol. 2, pp. 447–521, 1987.

K. Fugimura and H. Samet, “A hierarchical strategy for path planning among moving obstacles,” IEEE Transactions on Robotics and Automation, vol. 5, pp. 61–69, 1989.

L. Ulrich and J. Borenstien, “Vfh+: Reliable obstacle avoidance for fast mobile robots,” in Proceedings of the IEEE International Conference on Robotics and Automation, 1998, pp. 1572–1577.

N. Ko and R. Simmons, “The lane-curvature method for local obstacle avoidance,” in International Conference on Intelligence Robots and Systems, 1998, pp. 1615–1621.

J. Minguez and L. Montano, “Nearest diagram navigation. a new realtime collision avoidance approach,” in International Conference on Intelligence Robots and Systems, 2000, pp. 2094–2100.

T. Fraichard, “Planning in dynamic workspace: a state-time space approach,” Advanced Robotics, vol. 13, pp. 75–94, 1999.

D. H. R. K. J.-C. Latombe and S. Rock, “Randomized kinodynamic motion planning with moving obstacles,” Algorithmics and Computational Robotics, vol. 4, pp. 247–264, 2000.

O. Brock and O. Khatib, “Real time replanning in high- dimensional configuration spaces using sets of homotopic paths,” in Proceedings of the IEEE International Conference on Robotics and Automation, 2000, pp. 550–555.

N. S. J. Minguez L. Montano and R. Alami, “Global nearest diagram navigation,” in Proceedings of the IEEE International Conference on Robotics and Automation, 2001, pp. 33–39.

E. Feron and M. D. E. Frazzoli, “Real time motion planning for agile autonomous vehicles,” AIAA Journal of Guidance Control and Dynamics, vol. 25, pp. 116–129, 2002.

D. Fox, W. Burgard, and S. Thrun, “The dynamic window approach to collision avoidance,” IEEE Robotics and Automation Magazine, vol. 4, pp. 23–33, 1997.

T. Wikman and W. N. M.S. Branicky, “Reflexive collision avoidance: a generalized approach,” in Proceedings of the IEEE International Conference on Robotics and Automation, 1993, pp. 31–36.

S. L. J. Kuffner, “Randomized kinodynamic planning,” International Journal of Robotics Research, vol. 20, pp. 378–400, 2001.

T. Fraichard, “A short paper about safety,” in Proceedings of the IEEE International Conference on Robotics and Automation, 2007, pp. 1140–1145.

S. P. T. Fraichard, “Safe motion planning in dynamic environment,” in International Conference on Intelligence Robots and Systems, 2005, pp. 885–897.

T. Fraichard and H. Asama, “Inevitable collision state-a step towards safer robots?” Advanced Robotics, vol. 18, pp. 1001–1024, 2004.

N. Chan and M. Z. J. Kuffner, “Improved motion planning speed and safety using region of inevitable collision,” in ROMANSY, July 2008, pp. 103–114.

O. Gal, Z. Shiller, and E. Rimon, “Efficient and safe on-line motion planning in dynamic environment,” in Proceedings of the IEEE International Conference on Robotics and Automation, 2009, pp. 88–93.

Z. S. F. Large and S. Sekhavat, “Motion planning in dynamic environments: Obstacle moving along arbitrary trajectories,” in Proceedings of the IEEE International Conference on Robotics and Automation, 2001, pp. 3716–3721.

Z. S. O. Gal and T. Fraichard, “The nonlinear velocity obstacle revisited: the optimal time horizon,” in Workshop of Safety Motion Planning 2010.

P. Fiorini and Z. Shiller, “Motion planning in dynamic environments using velocity obstacles,” International Journal of Robotics Research, vol. 17, pp. 760–772, 1998.

S. Sundar and Z. Shiller, “Time optimal obstacle avoidance,” in Proceedings of the IEEE International Conference on Robotics and Automation, 1995, pp. 3075–3080.

S. Sundar, “Near-time optimal feedback control of robotic manipulators,” Ph.D. dissertation, UCLA, 1995.


Refbacks

  • There are currently no refbacks.




Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.