【导语】：一个实现了机器人技术中常用的路径规划算法的开源库，还有动图直观演示运行过程。该库公开时间不长，在 GitHub 已有 1200+ Star。

简介

在机器人研究领域，给定某一特定任务之后，如何规划机器人的运动方式至关重要。PathPlanning 是使用 Python 实现的存储库，实现了机器人技术中常用的路径规划算法。开发者还为每个算法设计了动画来演示运行过程，相当直观清晰。

项目地址：

https://github.com/zhm-real/PathPlanning

这个项目的贡献者目前是 4 位国内开发者。

目录结构

PathPlanning 库实现的路径规划算法包括基于搜索和基于采样的规划算法，目录结构如下：

下面我们直接通过开发者设计的动图了解各个算法的运行过程：

基于搜索的路径规划算法

（1）最佳路径优先搜索算法

"""Best-First Searching@author: huiming zhou"""import osimport sysimport mathimport heapqsys.path.append(os.path.dirname(os.path.abspath(__file__)) +                "/../../Search_based_Planning/")from Search_2D import plotting, envfrom Search_2D.Astar import AStarclass BestFirst(AStar):    """BestFirst set the heuristics as the priority     """    def searching(self):        """        Breadth-first Searching.        :return: path, visited order        """        self.PARENT[self.s_start] = self.s_start        self.g[self.s_start] = 0        self.g[self.s_goal] = math.inf        heapq.heappush(self.OPEN,                       (self.heuristic(self.s_start), self.s_start))        while self.OPEN:            _, s = heapq.heappop(self.OPEN)            self.CLOSED.append(s)            if s == self.s_goal:                break            for s_n in self.get_neighbor(s):                new_cost = self.g[s] + self.cost(s, s_n)                if s_n not in self.g:                    self.g[s_n] = math.inf                if new_cost < self.g[s_n]:  # conditions for updating Cost                    self.g[s_n] = new_cost                    self.PARENT[s_n] = s                    # best first set the heuristics as the priority                     heapq.heappush(self.OPEN, (self.heuristic(s_n), s_n))        return self.extract_path(self.PARENT), self.CLOSEDdef main():    s_start = (5, 5)    s_goal = (45, 25)    BF = BestFirst(s_start, s_goal, 'euclidean')    plot = plotting.Plotting(s_start, s_goal)    path, visited = BF.searching()    plot.animation(path, visited, "Best-first Searching")  # animationif __name__ == '__main__':    main()

（2）Dijkstra搜索算法

（3）A*搜索算法

（4）双向A* 搜索算法

（5）重复 A*搜索算法

（6）ARA* 搜索算法

（7）LRTA* 搜索算法

（8）RTAA* 搜索算法

（9）D* 搜索算法

（10）终身规划 A* 搜索算法

此处应为动图，图片过大，因无法上传，截图处理

（11）Anytime D* 搜索算法：变动较小

（12）Anytime D* 搜索算法：变动较大

基于采样的路径规划算法

（1）RRT 算法

（2）目标偏好 RRT 算法

（3）RRT_CONNECT 算法

（4）Extended_RRT 算法

此处应为动图，图片过大，因无法上传，截图处理

（5）动态 RRT 算法

此处应为动图，图片过大，因无法上传，截图处理

（6）N = 10000 时，rrt * 算法

（7）N = 1000 时，rrt*-Smart 算法

（8）FMT* 算法

（9）N =1000 时，Informed rrt * 算法

此处应为动图，图片过大，因无法上传，截图处理

（10）BIT* 算法

以上是开发者设计的动画，是不是很直观生动呢？对路径规划算法感兴趣的童鞋可以到项目主页详细了解。

开源前哨 日常分享热门、有趣和实用的开源项目。参与维护 10万+ Star 的开源技术资源库，包括：Python、Java、C/C++、Go、JS、CSS、Node.js、PHP、.NET 等。