Journal of Applied and Computational Mechanics
Time Distance: A Novel Collision Prediction and Path Planning Method
Document Type : Research Paper
Authors
Department of Mechanical Engineering, K. N. Toosi University of Technology, Tehran, 1991943344, Iran
Abstract
In this paper, a new fast algorithm for path planning and a collision prediction framework for two dimensional dynamically changing environments are introduced. The method is called Time Distance (TD) and benefits from the space-time space idea. First, the TD concept is defined as the time interval that must be spent in order for an object to reach another object or a location. Next, TD functions are derived as a function of location, velocity and geometry of objects. To construct the configuration-time space, TD functions in conjunction with another function named "Z-Infinity" are exploited. Finally, an explicit formula for creating the length optimal collision free path is presented. Length optimization in this formula is achieved using a function named "Route Function" which minimizes a cost function. Performance of the path planning algorithm is evaluated in simulations. Comparisons indicate that the algorithm is fast enough and capable to generate length optimal paths as the most effective methods do. Finally, as another usage of the TD functions, a collision prediction framework is presented. This framework consists of an explicit function which is a function of TD functions and calculates the TD of the vehicle with respect to all objects of the environment.
Keywords
Main Subjects
Publisher’s Note Shahid Chamran University of Ahvaz remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
[1] Nilsson, N.J., A mobile automaton: An application of artificial intelligence techniques, Sri International Menlo Park Ca Artificial Intelligence Center, 1969.
[2] Hwang, Y.K., Ahuja, N., Gross motion planning—a survey, ACM Computing Surveys, 24(3), 1992, 219-291.
[3] Atyabi, A., Powers, D., Review of classical and heuristic-based navigation and path planning approaches, International Journal of Advancements in Computing Technology, 5(14), 2013, 1-13.
[4] Šeda, M., Roadmap methods vs. cell decomposition in robot motion planning, Proceedings of the 6th WSEAS international conference on signal processing, robotics and automation, Athens, Greece, 2007.
[5] Khatib, O., Mampey, L.M., Fonction decision-commande d’un robot manipulateur, Rep, 2(7), 1978, 156.
[6] Neville, H., Impedance Control: An Approach to Manipulation: Part I~III, Journal of Dynamic System, Measurement, and Control, 107, 1985, 1.
[7] Miyazaki, F., Arimoto, S., Takegaki, M., Maeda, Y., Sensory feedback based on the artificial potential for robot manipulators, IFAC Proceedings Volumes, 17(2), 1984, 2381-2386.
[8] Pavlov, V.V., Voronin, A.N., The method of potential functions for coding constraints of the external space in an intelligent mobile robot, Soviet Automatic Control, 17(6), 1984, 45-51.
[9] Khatib, O., Real-time obstacle avoidance for manipulators and mobile robots, Springer, New York, 1986.
[10] Kala, R., Warwick, K., Planning autonomous vehicles in the absence of speed lanes using an elastic strip, IEEE Transactions on Intelligent Transportation Systems, 14(4), 2013, 1743-1752.
[11] Rasekhipour, Y., Khajepour, A., Chen, S.K., Litkouhi, B., A potential field-based model predictive path-planning controller for autonomous road vehicles, IEEE Transactions on Intelligent Transportation Systems, 18(5), 2016, 1255-1267.
[12] Rasekhipour, Y., Fadakar, I., Khajepour, A., Autonomous driving motion planning with obstacles prioritization using lexicographic optimization, Control Engineering Practice, 77, 2018, 235-246.
[13] Ji, J., Khajepour, A., Melek, W.W., Huang, Y., Path planning and tracking for vehicle collision avoidance based on model predictive control with multiconstraints, IEEE Transactions on Vehicular Technology, 66(2), 2016, 952-964.
[14] Overmars, M.H., A random approach to motion planning, 1992.
[15] Svestka, P., A probabilistic approach to motion planning for car-like robots, 1993.
[16] Overmars, M.H., Svestka, P., A probablisitic learning approach to motion planning, 1994.
[17] Kavraki, L., Latombe, J.C., Randomized preprocessing of configuration for fast path planning, Proceedings of the 1994 IEEE International Conference on Robotics and Automation, San Diego, CA, USA, 1994.
[18] Kavraki, L.E., Svestka, P., Latombe, J.C., Overmars, M.H., Probabilistic roadmaps for path planning in high-dimensional configuration spaces, IEEE Transactions on Robotics and Automation, 12(4), 1996, 566-580.
[19] Švestka, P., Overmars, M.H., Motion planning for carlike robots using a probabilistic learning approach, International Journal of Robotics Research, 16(2), 1997, 119-143.
[20] LaValle, S.M., Rapidly-exploring random trees: A new tool for path planning, 1998.
[21] Elbanhawi, M., Simic, M., Sampling-based robot motion planning: A review, IEEE Access, 2, 2014, 56-77.
[22] LaValle, S.M., Planning algorithms, Cambridge University Press, Cambridge, 2006.
[23] Ignat’ev, M.B., Kulakov, F.M., Pokrovski˘I, A.M., Robot-manipulator control algorithms, Joint Publications Research Service, 1973.
[24] Lozano-Pérez, T., Wesley, M.A., An algorithm for planning collision-free paths among polyhedral obstacles, Communications of the ACM, 22(10), 1979, 560-570.
[25] Rowat, P.F., Representing spatial experience and solving spatial problems in a simulated robot environment, Ph.D. Thesis, University of British Columbia, 1979.
[26] Holland, J.H., Adaptation in Natural and Artificial Systems, University of Michigan Press, Ann Arbor, 1975.
[27] Kennedy, J., Eberhart, R., Particle swarm optimization, Proceedings of ICNN'95-international conference on neural networks, 4, 1995, 1942-1948.
[28] Dorigo, M., Maniezzo, V., Colorni, A., Positive feedback as a search strategy, Politecnico di Milano, 1991.
[29] Dorigo, M., Optimization, learning and natural algorithms, Ph.D. Thesis, Politecnico di Milano, 1992.
[30] Dorigo, M., Maniezzo, V., Colorni, A., Ant system: optimization by a colony of cooperating agents, IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 26(1), 1996, 29-41.
[31] Mac, T.T., Copot, C., Tran, D.T., De Keyser, R., Heuristic approaches in robot path planning: A survey, Robotics and Autonomous Systems, 86, 2016, 13-28.
[32] Erdmann, M., Lozano-Perez, T., On multiple moving objects, Algorithmica, 2(1), 1987, 477-521.
[33] Cefalo, M., Oriolo, G., A general framework for task-constrained motion planning with moving obstacles, Robotica, 37(3), 2019, 575-598.
[34] Schwesinger, U., Siegwart, R., Furgale, P., Fast collision detection through bounding volume hierarchies in workspace-time space for sampling-based motion planners, 2015 IEEE International Conference on Robotics and Automation (ICRA), Seattle, Washington, USA, 2015.
[35] Xidias, E.K., Aspragathos, N.A., Motion planning for multiple non-holonomic robots: a geometric approach, Robotica, 26(4), 2008, 525-536.
[36] Alonso-Mora, J., Montijano, E., Nägeli, T., Hilliges, O., Schwager, M., Rus, D., Distributed multi-robot formation control in dynamic environments, Autonomous Robots, 43(5), 2019, 1079-1100.
[37] Ragaglia, M., Zanchettin, A.M., Rocco, P., Trajectory generation algorithm for safe human-robot collaboration based on multiple depth sensor measurements, Mechatronics, 55, 2018, 267–281.
[38] Gaschler, A., Petrick, R.P., Khatib, O., Knoll, A., KABouM: Knowledge-level action and bounding geometry motion planner, Journal of Artificial Intelligence Research, 61, 2018, 323-362.
[39] Cadkhodajafarian, A., Analooee, A., Azadi, S., Kazemi, R., Collision-free navigation and control for autonomous vehicle in complex urban environments, Modares Mechanical Engineering, 17(11), 2018, 277-288.
[40] Analooee, A., Kazemi, R., Azadi, S., SCR-Normalize: A novel trajectory planning method based on explicit quintic polynomial curves, Proceedings of the Institution of Mechanical Engineers, Part K: Journal of Multi-body Dynamics, 234(4), 2020, 650-674.
[41] Kala, R., Code for Robot Path Planning using Rapidly-exploring Random Trees, Indian Institute of Information Technology, Allahabad, 2014.
[42] Kala, R., Code for robot path planning using Bidirectional Rapidly-exploring Random Trees, Indian Institute of Information Technology, Allahabad, 2014.
[43] Kala, R., Code for robot path planning using Probabilistic Roadmap, Indian Institute of Information Technology, Allahabad, 2014.
[44] Kala, R., Code for robot path planning using A* algorithm, Indian Institute of Information Technology, Allahabad, 2014.
)
