查看原文
其他

开源了!机器人技术常用的路径规划算法(含动画演示)

小秋 开源前哨 2021-02-01

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


简介


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


项目地址:

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


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


目录结构


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

 


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


基于搜索的路径规划算法


(1)最佳路径优先搜索算法

 

"""
Best-First Searching
@author: huiming zhou
"""


import os
import sys
import math
import heapq

sys.path.append(os.path.dirname(os.path.abspath(__file__)) +
                "/../../Search_based_Planning/")

from Search_2D import plotting, env
from Search_2D.Astar import AStar


class 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.CLOSED


def main():
    s_start = (55)
    s_goal = (4525)

    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")  # animation


if __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* 算法

 


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


- EOF - 


更多优秀开源项目(点击下方图片可跳转)



如果觉得本文介绍的开源项目不错,欢迎转发推荐给更多人。



分享、点赞和在看

支持我们分享更多优秀开源项目,谢谢!

    您可能也对以下帖子感兴趣

    文章有问题?点此查看未经处理的缓存