With the high demand of more and more complicated fabrication scenario, during robotic fabrication, to verify if the robotic arm is in collision with existing building structure beforehand is very time consuming or even impossible. A detection of obstacle and autonomously avoid it is very essential in future fabrication circumstances. Therefore, I tried to find a solution to avoid obstacle(s) both in a pre-defined way and autonomous way. I found a path finding algorithm called A* search algorithm, which is widely used in game design and other graphics.
There are a lot of explanations of A* algorithms. To understand how it works, I mostly read two articles. Introduction to A star from Stanford University and A* Pathfinding for Beginners (very detailed and understandable) by Patrick Lester. Basically A* works based on grids called “Nodes”, every time the algorithm search for adjacent nodes and evaluate the nodes according to a key function F(n) = G(n) + H(n), where G(n) is the movement cost to move from the starting node to given node n, and H(n) is the estimated movement cost to move from node n to the final destination, which is called heuristic function. The node moves from start point, to adjacent least F value node until reaching destination, then a path is generated.
pathfinding component
Based on the algorithm and some sample codes, I wrote a grasshopper component, which just needs the start point, the destination point and obstacles. Inside this component, simply speaking, the space including two points and obstacles are subdivided into voxels, as “nodes” for A*, and voxels which collide with obstacles are defined non-walkable. Then run the algorithm and get the result.
In this component, the obstacles are given to the agent once before the calculation, and the path is generated and decided, which is often the situation for pre-defined known space and objects, like fabrication of robotic arm. But a more complicated situation is that if the agent doesn’t know where the obstacles are in the space, he has to explore the space and react to obstacles instantly, which is called autonomous path finding.
autonomous pathfinder
This is a python object that has a class which autonomously move to destination point and simultaneously detect obstacle, recalculate the path to destination in each step. Different with the previous component, this object doesn’t know the obstacles beforehand and requires calculation in each step. This results in a more accurate path since in each step the space is subdivided and the closer to destination the higher subdivision it gets. While on the other hand, the calculation is also too heavy to be real-time (mainly because of subdivision of space instead of A* algorithm), there is still a chance to make it faster, which makes for sense for such as a drone or another independent working agent to use.
outlook
As far as I can see, path finding can be used in a varied range and depth. Using pre-defined path finding for robotic obstacle avoidance, using autonomous path finding for drone or other independent working agents, or even based on autonomous path-finding we can design multi-agent working space to avoid each other and also the structures that they build. And still there are different ways to use the algorithm. For instance in autonomous path finding, we can subdivide a working space with high accuracy then we can avoid this space initialization for each step, which could increase the process a lot.
Download Plugin: PathFinder
Download Examples: AutonomousPathFinder.gh, Environment.3dm