JournalofIntelligent&RoboticSystemshttps://doi.org/10.1007/s10846-017-0748-6L*Algorithm—ALinearComputationalComplexityGraphSearchingAlgorithmforPathPlanningAdam Niewola 1 ·Leszek Pods ¸ edkowski 1Received:13May2017/Accepted:22November2017©TheAuthor(s)2017.ThisarticleisanopenaccesspublicationAbstractThe state-of-the-art graph searching algorithm applied to the optimal global path planning problem for mobile robots isthe A* algorithm with the heap structured open list. In this paper, we present a novel algorithm, called the L* algorithm,which can be applied to global path planning and is faster than the A* algorithm. The structure of the open list with theuse of bidirectional sublists (buckets) ensures the linear computational complexity of the L* algorithm because the nodes inthe current bucket can be processed in any sequence and it is not necessary to sort the bucket. Our approach can maintainthe optimality and linear computational complexity with the use of the cost expressed by floating-point numbers. The paperpresents the requirements of the L* algorithm use and the proof of the admissibility of this algorithm. The experimentsconfirmed that the L* algorithm is faster than the A* algorithm in various path planning scenarios. We also introduced amethod of estimating the execution time of the A* and the L* algorithm. The method was compared with the experimentalresults.Keywords Computational complexity · Graph searching · A* Algorithm · Shortest path planning · Bucket priority queue1 IntroductionThe graph searching algorithms are used for variousapplications. One of them is the mobile robot optimalpath planning. The optimal 1 path planning problem hasbeen widely investigated in the last 50 years. Many pathplanning methods for collision-free optimal path findingwere discovered and developed. They can be divided intotwo main groups:• roadmap methods (e.g., Voronoi diagrams [23], visibil-ity graphs [22], probabilistic roadmaps [24]),1 For the most of the path planning methods, the optimal path meansthe shortest path. In this paper, the experimental work presents thesolutions of the shortest path planning problem on 2D grid type mapsas well as the optimal path planning problem with respect to appliedoptimization criteria.? Adam Niewolaadam.niewola@gmail.comLeszek Pods ¸ edkowskilpodsedk@p.lodz.pl1Institute of Machine, Tools and Production Engineering,?ód´ z University of Technology, ?ód´ z, Poland• potential methods (e.g., potential fields [10]).The main focus of interest of this paper is the global pathplanning problem. It can be defined as a process of findingan ordered set of intermediate points connecting the startpoint and the goal point. Each point of this set must belocated in the free configuration space of the mobile robot.One of the most popular graph searching algorithmsis the A* algorithm. It was presented by Nilsson, Hart,and Raphael in 1968 [8]. It was widely investigated andcommonly used for developing new modified methods ofmobile robot path planning. In this paper, our algorithm willbe compared with the best version of the A* algorithm (withthe heap structured open list).For comparison of various algorithms, the notion of thecomputational complexity is used [1]. It says how fast thenumber of the basic operations of the algorithm increaseswith the growth of the input of the algorithm. The spacecomplexity says how fast the memory resources increasewith the increase of the input of the algorithm.In this paper, we present a new method of graphsearching, in particular, applied to the path planningproblem. It is a modification of the A* algorithm. TheL* algorithm uses a modified heuristic cost function anda modified open list based on the bucket structure. It is
