Comparison of path planning algorithms

Abstract

Path planning problems arise in many different fields such as; robotics, assembly analysis virtula prototyping, pharmaceutical drug design, manufacturing, and computer animation. Path planning algorithms aim to solve problems that involve computing a continuous sequence, a path, of configurations between an initial and goal configuration. Planning of a path involves some constraints, such as computing a collision-free path. We compared various path palnning and navigation algorithms. as reactive algorithm, an improved version of Artificial Potential Field (APF) algorithm is used. In robot coordination this algorithm is the superior algorithm. It coordinates 250 robots easily. whereas deliberative algorithms, such as Rapidly-exploring Random Tree Connect (RRT Connect) algorithm, can only coordinate 40 robots with high costs. The other deliberative algorithms, Rapidly-exploring Random Tree (RRT), Probebilistic Roadmap (PRM) and Lazy Probabilistic Roadmap (Lazy PRM), could not coordinate more than 20 robots within feasible resource and time limits in our tests. In robot coordination reactive algorithms are more succesful, but, when the environment contains local minima, using a deliberative algorithm iv inevitable. In path palnning for multiple robots, decentralized approaches, or partially grouping of the robots show better performances. As the number of the controlled robots in the environmental increases, using decentralized approaches becomes a requirement, because the amount of the required time and the resources increases exponentially in centralized approaches, but linearly in decentralized approaches. partially grouping of the robots gives the best performance results, because the resource requirements increase nearly linear, and nearby robots are controlled in centralized manner