Path planning is a fundamental problem in robotics. It may be stated as finding a path for a robot or agent, such that the robot or agent may move along this path from its initial configuration to goal configuration without colliding with any static obstacles or other robots or agents in the environment. Path planning algorithms are used in many fields, including bioinformatics, character animation, computer-aided design and computer-aided manufacturing (CAD/CAM), industrial automation, robotic surgery, and single and multiple robot navigation in both two and three dimensions.
In our studies we want to create a feasible and safety path to move autonomously our electric wheelchair in indoor environment.
The algorithm created can be divided in 3 different stages:
- Image elaboration
- Shortest path using A*
- Optimization with rubber band algorithm
During the first stage the path planner take the image of the map as input together to the initial and final wanted point. It elaborates the image and take care of walls, doors and size of robot in order to generate the map of the free space for the POC (Point of control) of the robot.
In the second stage the planner calculates the shortest path that connects the initial and the final point using the well-known “A* algorithm”. It returns a path that run very close to walls and with sharp corners in which the robot have to stop-rotate an then restart.
Therefore a stage of optimization is needed. The revisited version of the rubber band algorithm is used for this task.
The path obtained from the previous stage is turned into a series of masses and springs while the walls create a potential field of repulsion. Every single mass now sense the elastic force and the potential field, this leads to a movement of every single mass in it’s point of equilibrium.
Setting properly the stiffness of the springs leads to obtain a path that is far away from the walls and w/o discontinuity in the graph of the curvature.
All of this is not enough for us. Another important task is to generate this path in a very fast way. So, the algorithm was optimized even in this sense and, at the end, it produces outputs only 300 milliseconds after input received.
For testing the whole work were created three different application:
- A console application (for friends it’s the NERD application) in which all commands and communications are written in white over black;
- A console application (for friends it’s the NERD application) in which all commands and communications are written in white over black;
- A Unity based Virtual reality application in which you can see a virtual wheelchair that follows the path from the previous position to the selected final point.
The optimized path is visually better than the A* path even if it’s a bit longer. Viewing the graph of Curvature over distance, is easy to see that the blue line (optimized one) is smoother and with maximum absolute value lower than the yellow one.
The last graph is showing the comfort perceived by the user seated on the wheelchair. You can see that the wheelchair is very comfortable at a speed of 0.2 m/s.
Thanks for reading and remember… Don’t try this at home!
