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.
… excerpt ends here. Continue reading the full article.
