What is motion planning?
Motion planning is a very common topic in robotics. Motion planning involves searching for a path (potentially the optimal path) from point A to point B. Most of the time, in this problem, there are obstacles that can’t be passed through.
Advancing current ideas:
The idea of path-finding isn’t a very hard one, at least in the realm of computer science. A large chunk of people know how to solve a maze using DFS (Depth First Search) or BFS (Breadth First Search). There are a bunch of algorithms that work on prebuilt graphs. However, the two primary ideas that advance these current ideas include:
If there were just a bunch of polygons thrown in front of a pathfinding robot, where exactly are the nodes? Most are familiar with searching the graph when it is denoted as an array of [u,v] pairs where it shows a connection between u and v. What if these connections were gone and you were forced to make your own based on the obstacles?
- What if the pathfinding robot had a size, eliminating some possible paths? Let’s say that you were able to get nodes established. If the robot was a scalene triangle that could rotate, where do the nodes actually need to be? What gaps can it actually make it through?
Making a Path from Obstacles:
Creating a path based on a bunch of obstacles uses the idea of making a trapezodail map. The idea of a trapezodial map is discussed more in depth in another article in this section. Just assume that the algorithm for the trapezoid map has run and resulted in the following map.
The map is good, but not perfect for our current scenario. A few modifications need to be made. First, we want to remove all of the parts of the line that go through an obstacle so we don’t accidentally account for them. With this done, graph nodes can finally be placed. In each line segment, a graph node will be placed, and in every trapezoid section, there will also be a node. Now the graph can be made by connecting the “neighboring points”. This includes connecting the cell points to the points that lie on the edges of the cell.
The position of these nodes may change. Assuming the robot that is traversing the area doesn’t have to worry about how big it is, Points can be super close to the shapes. But if the robot has a shape that it should be worried about, a little more caution should be taken.
What if the robot has size?
Most people generally deal with robots, which have no size and are therefore allowed to fit through any small crevase. Now that size has been introduced, it generates a lot of different issues. When it comes to a robot of any size now, the idea of rotation might come into play. When the pathfinding robot had no size, there was no reason to rotate, as turning itself would not make it easier to get through any gaps. When the shape of the robot is a rectangle, It might not be able to fit through a gap initially, but if it turns itself, it might be able to squeeze through.
As is already common knowledge, the robot cannot go through obstacles. Since dealing with a robot of this size is extremely annoying, computer scientists attempted to reduce the problem. By making the size of the robot zero but altering the obstacles instead. Introduce the configuration space. An extra layer extends beyond the obstacles. The configuration space is meant to represent the space the robot can no longer traverse due strictly to its shape and size.
Now that the size is accounted for by the configuration space the size of the robot can not be set to 0. So, now the robot is not allowed to step into the configuration space as it is impossible to orientate itself so that it fits. The trapezodal map will not be made from the configuration space and everything can be operated without the worry of size.
Calulating the Configuration Area
Calculating the configuration area builds off the idea of a Minkowski sum. More or less in a Minkowski sum, one of the conex shapes is appended onto the other convex shape at every single point on its boundary. In this case, we will be applying the shape of the pathfinding robot to all of the obstacles. However, it is impossible to get every single point; is it possible to simulate it?
Method 1 (look for extra resources for proofs):
The first method is very simple but unfortunately works in O(n * m) time. Take an obstacle and find all of its points. At each of the obstacle points, append the robot’s shape, and make sure to also label the new points produced. After this has been done for every single point on the obstacle, take the convex hull with all of the points, including the new points created from appending the shapes
Method 2 (look for extra resources for proofs):
The Minkowski sum is made up of the sides of the robot sum, or obstacle. Using the angles, it is possible to calculate which edge corresponds with the other edge. Starting from the lowest point in both shapes, “draw” a straight line. Calculate the angle between the shape and the straight line (refer to the image for specifics). Whichever shape has a smaller angle, then that edge that was used in the Minkowski sum.
Now that the configuration area has been established, the same method mentioned previously can be used to create a graph of the area. Create the trapezoidal map, put graph nodes, and connect as was mentioned before. Now, a simple algorithm for searching, like BFS or DFS, can be used to search the graph. If the true distance between nodes is calculated, then an algorithm like A* can be used to get optimal paths.