Global Path Planning Algorithm of Multi-Bug
CSTR:
Author:
Affiliation:

Clc Number:

Fund Project:

  • Article
  • |
  • Figures
  • |
  • Metrics
  • |
  • Reference
  • |
  • Related
  • |
  • Cited by
  • |
  • Materials
  • |
  • Comments
    Abstract:

    Path planning is one of the key technologies to realize its ability of autonomous action in complex environment. A nonsearch global path planning algorithm called MultiBug was proposed. It combined the merits of short path length of global path planning and small computation cost of the Bug algorithms, which generated better overall performance compared with traditional path planning methods. This method had great advantages in the situation of high timeliness and general path requirements. In the MultiBug algorithm, the simple pathfinding logic that followed the wall in the Bug algorithm was adopted, and bug splitting and death rules were added into the framework. The algorithm was ended when one of the bugs arrived at the target or all of the bugs met the death rules and dead, which permitted multipath parallel computation for local optimal planning solution. Grid maps, including multiple types of obstacles and various mazes, were used to testify the MultiBug algorithm. In order to ensure the reliability of operation results, each algorithm in the same grid map was run 10 times, and its operation time was averaged. Compared with DistBug algorithm, RRT* and A* algorithms, it showed much better performance stability in terms of the path length and the computational time cost. Especially when compared with the A* algorithm, which provided the shortest path length, it decreased the calculation time by more than four fifths with grid map size as 50×50 and only increased the path length by less than one fifth. In 500×500 grid map, the time was less than one tenthousandth of that of A* algorithm. By the theoretical analysis and the simulation verification, MultiBug algorithm had a time complexity as O(n), provided relatively short path, required less computational cost, and had good stability and versatility for various environments.

    Reference
    Related
    Cited by
Get Citation
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:October 31,2019
  • Revised:
  • Adopted:
  • Online: June 10,2020
  • Published:
Article QR Code