Pathfinder – part 2. My results
Finally, I’m done with pathfinder. It has been developed in C# and WPF, and is nice application in my opinion. I have published some videos that present pathfinder’s capabilites. Watch them below. It was a hard work to complete this task and pleasure to see it working quite efficiently. My pathfinder is fully scalable, this means that path computations are perfomed parallely in order to achieve high performance. The are some interesting topics which I would like to share on this blog so there is going to be a series of Pathfinder posts. In the previous I was writing about solving nonlinear polynomial systems. This was deeply correlated with the work I have finished with my pathfinder project. Please note, that a robot is completely defined by user in my pathfinder application (see videos below). So whenever I’m solving Inverse Kinematics and polynomial systems, I always have to solve it in the full domain of equations beacuse I don’t know the robot’s equations since defining it on UI. This was a problem, because the numerical methods should be globally convergent. The Newton-Raphson method I have implemented here has been described int the previous post. In the next posts in series I’ll write some miscellaneous information about pathfinding and code. A general discussion of higher-dimensional pathfinder will be in the last post in series.
The photos above illustrate the basic concept of that has been done. The robot with two revolute joints is located by user somewhere on the screen. We select an additional destination point, add geometrical constraints (ellipses, rectangles or triangles are available) and the robot should reach the destination point. This is pathfinder problem with geometrical constraints. You can set following options in my program:
- Add geometrical constraints (ellipses, rectangles or triangles)
- Move robot on a screen with a mouse and adjust its properties using intuitive UI controls
- Select robot’s destination point within an intuitive mouse move
- Quickly play with ‘on mouse move’ robot’s Inverse kinematics solution.
- Watch and analyze the generated 2C Configuration Space
- Choose Inverse Kinematics polynomial solvers (either Newton-Raphson with user-defined initial steps) or geometrical. If you prefer Newton-Raphson you can set the start point in a control.
- Choose pathfinding algorithm (A-Star) properties. This means:
- Choose different heuristics coefficient. Heuristics is used in A-Star algorithm
- Adjust algorithm step which A-Star uses in finding neighbourhood. The smaller value you set, the more accurate path you’ll get and the longer it will take to compute a path.
- Choose satisfying error A-Star is going to be run. The smaller value you set, the more accurate path you’ll get.
- Adjust maximal algorithm runtime. In case where no solution to the problem exists there is no sense in waiting while A-Star runs out of all closed vertices. The reasonable time which I was using was up to 5 minutes. If it doesn’t find a solution it’s reasonable to switch to diffusive search and start searching with it. This maximal time, so if geometrical constraints are simple, AStar runs almost on-the-fly. The more complex scene you build, the more time you will need to get the path solved.
- Animate a robot on a generated path