New Sampling Based Planning Algorithm for Local Path Planning for Autonomous Vehicles

Author

Muhammad Aria Rajasa Pohan, M.T

Abstrak

The purpose of this paper was to design a new sampling-based planning algorithm based on the integration of Rapidly-exploring Random Trees (RRT) and Probabilistic Roadmap Method (PRM) algorithms that could be used to build local path planning for autonomous vehicles. The RRT algorithm had the advantage of low computational time but provided suboptimal solutions, while the PRM algorithm had the advantage of providing asymptotically optimal solutions, but high computational time. Then the proposed algorithm combined the advantages of the two algorithms so that they had low computational time and provided optimal asymptotic solutions. The process was carried out by running the RRT algorithm several times to obtain several alternative suboptimal paths. Furthermore, the optimal solution was built using these suboptimal pathways, using the PRM-Djikstra path optimization algorithm. After the algorithm produced the final path, smoothing techniques using the Reed Sheep Planner algorithm employed to produce a smooth curved path. This study also compared the effect of using several variations of the RRT algorithm. With, tested algorithm in motion-planning problems of the nonholonomic vehicle. The results showed that our algorithm could produce higher quality output paths because the algorithm generated several sub-optimal paths and then combines them. Keywords: Autonomous vehicles, Djikstra, Local path planning, Probabilistic roadmap method, Rapidly-exploring random trees.