Real-Time Path Planning is a term used in robotics that consists of motion planning methods that can adapt to real time changes in the environment. This includes everything from primitive algorithms that stop a robot when it approaches an obstacle to more complex algorithms that continuously takes in information from the surroundings and creates a plan to avoid obstacles.
These methods are different from something like a Roomba robot vacuum as the Roomba may be able to adapt to dynamic obstacles but it does not have a set target. A better example would be Embark self-driving semi-trucks that have a set target location and can also adapt to changing environments.
The targets of path planning algorithms are not limited to locations alone. Path planning methods can also create plans for stationary robots to change their poses. An example of this can be seen in various robotic arms, where path planning allows the robotic system to change its pose without colliding with itself.
As a subset of motion planning, it is an important part of robotics as it allows robots to find the optimal path to a target. This ability to find an optimal path also plays an important role in other fields such as video games and gene sequencing.
Concepts
In order to create a path from a target point to a goal point there must be classifications about the various areas within the simulated environment. This allows a path to be created in a 2D or 3D space where the robot can avoid obstacles.
Work Space
The work space is an environment that contains the robot and various obstacles. This environment can be either 2-dimensional or 3-dimensional.
Configuration Space
The configuration of a robot is determined by its current position and pose. The configuration space is the set of all configurations of the robot. By containing all the possible configurations of the robot, it also represents all transformations that can be applied to the robot.
Within the configuration sets there are additional sets of configurations that are classified by the various algorithms.
Free Space
The free space is the set of all configurations within the configuration space that does not collide with obstacles.
Target Space
The target space is the configuration that we want the robot to accomplish.
Obstacle Space
The obstacle space is the set of configurations within the configuration space where the robot is unable to move to.
Danger Space
The danger space is the set of configurations where the robot can move through but does not want to. Oftentimes robots will try to avoid these configurations unless they have no other valid path or are under a time restraint. For example, a robot would not want to move through a fire unless there were no other valid paths to the target space.
Methods
Global
Global path planning refers to methods that require prior knowledge of the robot's environment. Using this knowledge it creates a simulated environment where the methods can plan a path.
Rapidly Exploring Random Tree (RRT)
The rapidly exploring random tree method works by running through all possible translations from a specific configuration . By running through all possible series of translations a path is created for the robot to reach the target from the starting configuration.
Local
Local path planning refers to methods that take in information from the surroundings in order to generate a simulated field where a path can be found. This allows a path to be found in the real-time as well as adapt to dynamic obstacles.
Probabilistic Roadmap (PRM)
The probabilistic roadmap method connects nearby configurations in order to determine a path that goes from the starting to target configuration. The method is split into two different parts: preprocessing phase and query phase. In the preprocessing phase, algorithms evaluate various motions to see if they are located in free space. Then in the query phase, the algorithms connects the starting and target configurations through a variety of paths. After creating the paths, it uses Dijkstra's shortest path query to find the optimal path.
Evolutionary Artificial Potential Field (EAPF)
The evolutionary artificial potential field method uses a mix of artificial repulsive and attractive forces in order to plan a path for the robot. The attractive forces originate from the target which leads the path to the target in the end. The repulsive forces come from the various obstacles the robot will come across. Using this mix of attractive and repulsive forces, algorithms can find the optimal path.
Indicative Route Method (IRM)
The indicative route method uses a control path towards the target and an attraction point located at the target. Algorithms are often used to find the control path, which is oftentimes the path with the shortest minimum-clearance path. As the robot stays on the control path the attraction point on the target configuration leads the robot towards the target.
Modified Indicative Routes and Navigation (MIRAN)
The modified indicative routes and navigation method gives various weights to different paths the robot can take from its current position. For example, a rock would be given a high weight such as 50 while an open path would be given a lower weight such as 2. This creates a variety of weighted regions in the environment which allows the robot to decide on a path towards the target.
Applications
Humanoid Robots
For many robots the number of degrees of freedom is no greater than three. Humanoid robots on the other hand have a similar number of degrees of freedom to a human body which increases the complexity of path planning. For example, a single leg of a humanoid robot can have around 12 degrees of freedom. The increased complexity comes from the greater possibility of the robot colliding with itself. Real-time path planning is important for the motion of humanoid robots as it allows various parts of the robot to move at the same time while avoiding collisions with the other parts of the robot.
For example, if we were to look at our own arms we can see that our hands can touch our shoulders. For a robotic arm this may pose a risk if the parts of the arms were to collide unintentionally with each other. This is why path planning algorithms are needed to prevent these accidental collisions.
Self-Driving Vehicles
Self-driving vehicles are a form of mobile robots that utilizes real-time path planning. Oftentimes a vehicle will first use global path planning to decide which roads to take to the target. When these vehicles are on the road they have to constantly adapt to the changing environment. This is where local path planning methods allow the vehicle to plan a safe and fast path to the target location.
An example of this would be the Embark self-driving semi-trucks, which uses an array of sensors to take in information about their environment. The truck will have a predetermined target location and will use global path planning to have a path to the target. While the truck is on the road it will use its sensors alongside local path planning methods to navigate around obstacles to safely reach the target location.
Video games
Oftentimes in video games there are a variety of non-player characters that are moving around the game which requires path planning. These characters must have paths planned for them as they need to know where to move to and how to move there.
For example, in the game Minecraft there are hostile mobs that track and follow the player in order to kill the player. This requires real-time path planning as the mob must avoid various obstacles while following the player. Even if the player were to add additional obstacles in the way of the mob, the mob would change its path to still reach the player.
References
- ^ Hui-Zhong Zhuang; Shu-Xin Du; Tie-Jun Wu (2005). "Real-Time Path Planning for Mobile Robots". 2005 International Conference on Machine Learning and Cybernetics. IEEE. pp. 526–531. doi:10.1109/icmlc.2005.1527001. ISBN 0780390911. S2CID 23851845.
- Jackson, Russell C.; Çavuşoğlu, M. Cenk (2013-12-31). "Needle path planning for autonomous robotic surgical suturing". 2013 IEEE International Conference on Robotics and Automation. Vol. 2013. pp. 1669–1675. doi:10.1109/ICRA.2013.6630794. ISBN 978-1-4673-5643-5. ISSN 2152-4092. PMC 3966119. PMID 24683500.
- ^ LaValle, Steven (2006). Planning Algorithms. Cambridge University Press. pp. 127–128.
- ^ Jahanshahi, Hadi; Jafarzadeh, Mohsen; Sari, Naeimeh Najafizadeh; Pham, Viet-Thanh; Huynh, Van Van; Nguyen, Xuan Quynh (February 2019). "Robot Motion Planning in an Unknown Environment with Danger Space". Electronics. 8 (2): 201. doi:10.3390/electronics8020201.
- ^ Limone, Brett. "What is Global Path Planning & How Does it Compare to Local Path Planning?". www.energid.com. Retrieved 2019-10-15.
- LaValle, Steven (1998). Rapidly-exploring random trees: A new tool for path planning. Citeseer.
- Kavraki, Lydia E.; Latombe, Jean-claude (1998). Probabilistic Roadmaps for Robot Path Planning. CiteSeerX 10.1.1.41.4215.
- Leven, Peter; Hutchinson, Seth (2016-07-02). "A Framework for Real-time Path Planning in Changing Environments". The International Journal of Robotics Research. 21 (12): 999–1030. doi:10.1177/0278364902021012001. S2CID 11169688.
- Vadakkepat, P.; Kay Chen Tan; Wang Ming-Liang (July 2000). "Evolutionary artificial potential fields and their application in real time robot path planning". Proceedings of the 2000 Congress on Evolutionary Computation. CEC00 (Cat. No.00TH8512). Vol. 1. pp. 256–263 vol.1. doi:10.1109/CEC.2000.870304. ISBN 0-7803-6375-2. S2CID 16846787.
- Geraerts, R. (May 2010). "Planning short paths with clearance using explicit corridors". 2010 IEEE International Conference on Robotics and Automation. pp. 1997–2004. doi:10.1109/ROBOT.2010.5509263. ISBN 978-1-4244-5038-1. S2CID 1760187.
- Jaklin, Norman; Cook, Atlas; Geraerts, Roland (May 2013). "Real-time path planning in heterogeneous environments: Real-time path planning in heterogeneous environments". Computer Animation and Virtual Worlds. 24 (3–4): 285–295. doi:10.1002/cav.1511. S2CID 2350524.
- Fujita, Masahiro; Fukuchi, Masaki; Gutmann, Jens-Steffen (2005). "Real-Time Path Planning for Humanoid Robot Navigation". IJCAI. 2005. S2CID 1331595.
- Katrakazas, Christos; Quddus, Mohammed; Chen, Wen-Hua; Deka, Lipika (2015-11-01). "Real-time motion planning methods for autonomous on-road driving: State-of-the-art and future research directions". Transportation Research Part C: Emerging Technologies. 60: 416–442. Bibcode:2015TRPC...60..416K. doi:10.1016/j.trc.2015.09.011. hdl:2086/14646. ISSN 0968-090X.
- Hui, Jonathan (2018-04-18). "Self-driving car: Path planning to maneuver the traffic". Medium. Retrieved 2019-11-05.