【深蓝学院】移动机器人运动规划--第2章 基于搜索的路径规划--笔记

这篇具有很好参考价值的文章主要介绍了【深蓝学院】移动机器人运动规划--第2章 基于搜索的路径规划--笔记。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

0. Outline

【深蓝学院】移动机器人运动规划--第2章 基于搜索的路径规划--笔记,motion planning,笔记,Robotics,motion planning

1. Graph Search Basis

Configuration Space等概念
【深蓝学院】移动机器人运动规划--第2章 基于搜索的路径规划--笔记,motion planning,笔记,Robotics,motion planning
机器人配置: 指机器人位置和所有点的表示。
DOF: 指用于表示机器人配置所需的最小的实数坐标的数量n。
C-space: 包含机器人n维所有配置的空间。
在C-space中机器人的pose是一个点。

【深蓝学院】移动机器人运动规划--第2章 基于搜索的路径规划--笔记,motion planning,笔记,Robotics,motion planning

【深蓝学院】移动机器人运动规划--第2章 基于搜索的路径规划--笔记,motion planning,笔记,Robotics,motion planning

  • 机器人在C-space中被表示为一个点,pose包含为R,t
  • 空间中的障碍物也需要映射到C-space中,并且根据机器人的尺寸做膨胀(该过程是one-time work,可一次完成,因为如果点碰不到膨胀边缘,就不会碰到障碍物),叫做C-obstacle
  • S-space=(C-obstacle) U (C-free)
  • path是在C-free中从起点start到终点goal

eg:如果将机器人建模为一个半径为 δ r \delta_r δr的球,那么将obstacle向外膨胀 δ r \delta_r δr,即可对一个点进行palnning
【深蓝学院】移动机器人运动规划--第2章 基于搜索的路径规划--笔记,motion planning,笔记,Robotics,motion planning

2. Graph and Search Method

无向图,有向图,加权图(权值根据具体问题定义,可能是长度,可能是消耗的能量,可能是风险等等)

【深蓝学院】移动机器人运动规划--第2章 基于搜索的路径规划--笔记,motion planning,笔记,Robotics,motion planning
基于搜索的图有栅格,本身就包含关系,而基于采样的图则没有这种关系。
【深蓝学院】移动机器人运动规划--第2章 基于搜索的路径规划--笔记,motion planning,笔记,Robotics,motion planning
搜索的过程即构建搜索树的过程,但该过程往往代价较大,我们的目标是设计尽可能快且不失最优性的路径搜索算法。

【深蓝学院】移动机器人运动规划--第2章 基于搜索的路径规划--笔记,motion planning,笔记,Robotics,motion planning

【深蓝学院】移动机器人运动规划--第2章 基于搜索的路径规划--笔记,motion planning,笔记,Robotics,motion planning

【深蓝学院】移动机器人运动规划--第2章 基于搜索的路径规划--笔记,motion planning,笔记,Robotics,motion planning

DFS容器是栈,BFS容器是队列。

【深蓝学院】移动机器人运动规划--第2章 基于搜索的路径规划--笔记,motion planning,笔记,Robotics,motion planning

【深蓝学院】移动机器人运动规划--第2章 基于搜索的路径规划--笔记,motion planning,笔记,Robotics,motion planning
【深蓝学院】移动机器人运动规划--第2章 基于搜索的路径规划--笔记,motion planning,笔记,Robotics,motion planning

图示中DFS先顺时针,后逆时针,访问最大的,出栈,入栈。

【深蓝学院】移动机器人运动规划--第2章 基于搜索的路径规划--笔记,motion planning,笔记,Robotics,motion planning
图始终BFS始终逆时针,从小到大依次访问,出队,入队,不断地一层一层地推进frontier。

【深蓝学院】移动机器人运动规划--第2章 基于搜索的路径规划--笔记,motion planning,笔记,Robotics,motion planning
BFS回溯可以找到最短路径,而DFS不可以,所以常用DFS。(先有一个直观的印象)

贪心算法:
【深蓝学院】移动机器人运动规划--第2章 基于搜索的路径规划--笔记,motion planning,笔记,Robotics,motion planning
贪心算法依靠某种规则来挑选最优的节点,叫做启发。启发即对于最近节点的一个猜测,比如图中红色到紫色的距离有两种猜测:欧式距离和曼哈顿距离。

  • 无障碍物时贪心算法与BFS对比:
    【深蓝学院】移动机器人运动规划--第2章 基于搜索的路径规划--笔记,motion planning,笔记,Robotics,motion planning
    贪心算法又快又准。

  • 有障碍物时对比
    【深蓝学院】移动机器人运动规划--第2章 基于搜索的路径规划--笔记,motion planning,笔记,Robotics,motion planning
    贪心算法虽然快,但是陷入局部最优,而BFS虽然慢,但是路径确实全局最优。

虽然贪心算法有时不是最优,但仍然有很多我们可以借鉴的性质。

【深蓝学院】移动机器人运动规划--第2章 基于搜索的路径规划--笔记,motion planning,笔记,Robotics,motion planning
实际中需要考虑每小段路径的cost,即C,当每个C=1时,BFS最优,但通常情况C不为1,于是引入了Dijkstra和A*。

3. Dijkstra

算法流程可以看浙大的这节视频

【深蓝学院】移动机器人运动规划--第2章 基于搜索的路径规划--笔记,motion planning,笔记,Robotics,motion planning
dist最小可以使用priority_queue来实现,按照键值来排序,弹出键值最小的。

【深蓝学院】移动机器人运动规划--第2章 基于搜索的路径规划--笔记,motion planning,笔记,Robotics,motion planning
【深蓝学院】移动机器人运动规划--第2章 基于搜索的路径规划--笔记,motion planning,笔记,Robotics,motion planning
这里的priority queue就是open list,已经扩展过的(已经收录的node)放在close list中(实际上不是方node本身,只需使用容器管理这些node的下标)。


原来数据结构里面讲的Dijkstra和这里讲的Dijkstra,在实现上的不同在于:

  • 原来while()循环中一次只收录一个node;
  • 这里的while()循环,只要第一次遇到未被收录的node,就将其收录(也就是加入到open list中),并标记为已收录(id=1),下次遇到id=1的直接判断g值,并判断是否更新g值。(实际上这里的Diskstra算法在便利neighbors nodes时id只有0和1,即只有new node和node already in open list,被遍历完neighbor nodes的node,在下一次while循环中会被从open list中erase掉,并加入到close list中(set id to -1))

本质上两种实现方法相同,但是这里讲的方法结合了Dijkstra算法的BFS的“队列”的数据结构特性,所以更好理解,以下是本章作业中主要的A*实现(只是比Dijkstra多了个heuristic):

void AstarPathFinder::AstarGraphSearch(Vector3d start_pt, Vector3d end_pt)
{   
    ros::Time time_1 = ros::Time::now();    

    //index of start_point and end_point
    Vector3i start_idx = coord2gridIndex(start_pt);
    Vector3i end_idx   = coord2gridIndex(end_pt);
    goalIdx = end_idx;

    //position of start_point and end_point
    start_pt = gridIndex2coord(start_idx);
    end_pt   = gridIndex2coord(end_idx);

    //Initialize the pointers of struct GridNode which represent start node and goal node
    GridNodePtr startPtr = new GridNode(start_idx, start_pt);
    GridNodePtr endPtr   = new GridNode(end_idx,   end_pt);

    //openSet is the open_list implemented through multimap in STL library
    openSet.clear();
    // currentPtr represents the node with lowest f(n) in the open_list
    GridNodePtr currentPtr  = NULL;
    GridNodePtr neighborPtr = NULL;

    //put start node in open set
    startPtr -> gScore = 0;
    startPtr -> fScore = startPtr -> gScore + getHeu(startPtr,endPtr);
    //STEP 1: finish the AstarPathFinder::getHeu , which is the heuristic function
    startPtr -> id = 1; 
    startPtr -> coord = start_pt;
    openSet.insert( make_pair(startPtr -> fScore, startPtr) );//默认按照key升序排序
    /*
    STEP 2 :  some else preparatory works which should be done before while loop
    please write your code below
    */
    double tentative_gScore;
    vector<GridNodePtr> neighborPtrSets;
    vector<double> edgeCostSets;
    //计算graph中所有的node到start_pt的heuristic

    //将start node赋予地图(因为是刚才new出来的,不是直接从地图里面取出来的)
    GridNodeMap[start_idx(0)][start_idx(1)][start_idx(2)] = startPtr;
    // this is the main loop
    while ( !openSet.empty() ){
        /*
        step 3: Remove the node with lowest cost function from open set to closed set
        please write your code below
        
        IMPORTANT NOTE!!!
        This part you should use the C++ STL: multimap, more details can be find in Homework description
        */
        //弹出一个就要找到他所有的未被扩展的邻居
//        ROS_DEBUG("\nhere3");
        currentPtr = openSet.begin()->second;
        openSet.erase(openSet.begin());
        currentPtr->id = -1;//mark as visited

        // if the current node is the goal 
        if( currentPtr->index == goalIdx ){
            ros::Time time_2 = ros::Time::now();
            terminatePtr = currentPtr;
            ROS_WARN("[A*]{sucess}  Time in A*  is %f ms, path cost if %f m", (time_2 - time_1).toSec() * 1000.0, currentPtr->gScore * resolution );            
            return;
        }
        //get the succetion(找到currentPtr的neighbor nodes)
        AstarGetSucc(currentPtr, neighborPtrSets, edgeCostSets);  //STEP 4: finish AstarPathFinder::AstarGetSucc yourself     

        /*
        STEP 5:  For all unexpanded neigbors "m" of node "n", please finish this for loop
        please write your code below     
        */
        //在这个循环里面,id只会为0/1,为-1的都是遍历完之后被erase掉了
        for(int i = 0; i < (int)neighborPtrSets.size(); i++){
            neighborPtr = neighborPtrSets[i];
            tentative_gScore = currentPtr->gScore + edgeCostSets[i];
//            ROS_DEBUG("\nneighborPtr->id: %d", neighborPtr->id);
            /*
            Judge if the neigbors have been expanded
            please write your code below
            
            IMPORTANT NOTE!!!
            neighborPtrSets[i]->id = -1 : expanded, equal to this node is in close set
            neighborPtrSets[i]->id = 1 : unexpanded, equal to this node is in open set      
            */
            if(neighborPtr -> id == 0 ){ //discover a new node, which is not in the closed set and open set
                /*
                STEP 6:  As for a new node, do what you need do ,and then put neighbor in open set and record it
                please write your code below 
                */

                if(neighborPtr -> gScore == inf) {
                    neighborPtr->cameFrom = currentPtr;
                    neighborPtr -> gScore = tentative_gScore;
                    neighborPtr -> fScore = neighborPtr -> gScore + getHeu(neighborPtr, endPtr); //getHeu(startPtr,neighborPtr);
                    neighborPtr -> id = 1;//标记为expanded
                    openSet.insert( make_pair(neighborPtr->fScore, neighborPtr) );//加入到open list中,注意,这里需要使用fscore,而不是gscore,如果是gscore,就成了Dijkstra了
//                    ROS_DEBUG("\nneighborPtr -> gScore is inf");
                    continue;//这里可以直接退出本轮循环,因为下面的条件不会满足
                } else {
                    ROS_DEBUG_STREAM("\nA* here neighborPtr -> gScore is not inf");
                }
            }
            //这里不能取等,去等了如果前面在找neighbors时没有去掉本身,就会陷入自己来自于自己的bug
            if(tentative_gScore < neighborPtr-> gScore){ //this node is in open set and need to judge if it needs to update, the "0" should be deleted when you are coding
                /*
                STEP 7:  As for a node in open set, update it , maintain the openset ,and then put neighbor in open set and record it
                please write your code below  
                */
                neighborPtr -> cameFrom = currentPtr;
                neighborPtr -> gScore = tentative_gScore;
                neighborPtr -> fScore = neighborPtr -> gScore + getHeu(neighborPtr, endPtr);

            }
            //不满足条件的就是在close set中,不用处理,在下次的while循环中会被erase掉
        }      
    }
    //if search fails
    ros::Time time_2 = ros::Time::now();
    if((time_2 - time_1).toSec() > 0.1)
        ROS_WARN("Time consume in Astar path finding is %f", (time_2 - time_1).toSec() );
}

【深蓝学院】移动机器人运动规划--第2章 基于搜索的路径规划--笔记,motion planning,笔记,Robotics,motion planning

【深蓝学院】移动机器人运动规划--第2章 基于搜索的路径规划--笔记,motion planning,笔记,Robotics,motion planning

Pros:Dijkstra算法是完备且最优的:完备即一定能找到解;最优即解一定是最优的。
Cons:由于没有goal的任何信息,所以是盲目地,均匀地向各个方向扩散的。

【深蓝学院】移动机器人运动规划--第2章 基于搜索的路径规划--笔记,motion planning,笔记,Robotics,motion planning
结合贪心算法和info和Dijkstra的单源带权搜索,将二者的优点结合,引出了A*,相较于Dijkstra,在g值的计算方面添加了对goal的估计h,类似于DL中为loss添加正则项。

4. A*

4.1 算法介绍

【深蓝学院】移动机器人运动规划--第2章 基于搜索的路径规划--笔记,motion planning,笔记,Robotics,motion planning
A*与Dijkstra的唯一不同就是g值的计算,由单纯的 g ( n ) g(n) g(n)变为 f ( n ) = g ( n ) + h ( n ) f(n)=g(n)+h(n) f(n)=g(n)+h(n),其中所有节点的 h ( n ) h(n) h(n)是在初始化阶段one-time计算好的(如所有节点到goal的欧氏距离)。

【深蓝学院】移动机器人运动规划--第2章 基于搜索的路径规划--笔记,motion planning,笔记,Robotics,motion planning

4.2 A*最优性讨论

【深蓝学院】移动机器人运动规划--第2章 基于搜索的路径规划--笔记,motion planning,笔记,Robotics,motion planning
上例说明A* 不一定是最优的,

f A = 7 , f G = 5 f_A=7,f_G=5 fA=7,fG=5,A*找到的路径为S->G

而实际cost, g S G = 5 , g S A G = 4 g_{SG}=5,g_{SAG}=4 gSG=5,gSAG=4,显然SAG最优。

A*满足最优的条件:当所有节点的guess的h ≤ \leq 真实g

用实际数据来验证:

  1. h s = 6 , h A = 5 h_s=6,h_A=5 hs=6hA=5,则
    S : f = g + h = 0 + 6 = 6 S: f=g+h=0+6=6 S:f=g+h=0+6=6
    A : f = g + h = 1 + 5 = 6 A: f=g+h=1+5=6 A:f=g+h=1+5=6
    G : f = g + h = 5 + 0 = 5 G: f=g+h=5+0=5 G:f=g+h=5+0=5
    输出S->G,非最优。

  2. h s = 5 , h A = 4 h_s=5,h_A=4 hs=5hA=4,则
    S : f = g + h = 0 + 5 = 5 S: f=g+h=0+5=5 S:f=g+h=0+5=5
    A : f = g + h = 1 + 4 = 5 A: f=g+h=1+4=5 A:f=g+h=1+4=5
    G : f = g + h = 5 + 0 = 5 G: f=g+h=5+0=5 G:f=g+h=5+0=5
    输出方式涉及到路径对称性问题,在5.3节tie breaker中会详细讨论。

  3. h s = 5 , h A = 3 h_s=5,h_A=3 hs=5hA=3,均满足小于等于actual g g g,则
    S : f = g + h = 0 + 5 = 5 S: f=g+h=0+5=5 S:f=g+h=0+5=5
    A : f = g + h = 1 + 3 = 4 A: f=g+h=1+3=4 A:f=g+h=1+3=4
    G : f = g + h = 5 + 0 = 5 G: f=g+h=5+0=5 G:f=g+h=5+0=5
    pop A;
    pop G;
    输出S->A->G,最优。

于是重点就转移到了如何设计heuristic guess函数h

【深蓝学院】移动机器人运动规划--第2章 基于搜索的路径规划--笔记,motion planning,笔记,Robotics,motion planning

启发式函数需要满足 h ( n ) ≤ h ∗ ( n ) h(n)\leq h^*(n) h(n)h(n)
我们称这种启发式函数为admissible(可接受的、可容许的)的。

【深蓝学院】移动机器人运动规划--第2章 基于搜索的路径规划--笔记,motion planning,笔记,Robotics,motion planning
admissible heuristic function的本质为向量的范数,以下为一些admissible heuristic function的列举:

  • 欧式距离(向量2范数): ∣ ∣ x ∣ ∣ 2 = ∑ i = 1 n ∣ x i ∣ 2 ||x||_2=\sqrt{\sum\limits_{i=1}^{n} |x_i|^2} ∣∣x2=i=1nxi2 ,always admissible
  • 曼哈顿距离(向量1范数): ∣ ∣ ∣ x ∣ ∣ 1 = ∑ i = 1 n ∣ x i ∣ |||x||_1=\sum\limits_{i=1}^{n} |x_i| ∣∣∣x1=i=1nxi,Depends admissible
  • 向量的无穷范数: ∣ ∣ x ∣ ∣ ∞ = m a x i ( x i ) ||x||_{\infty}=\mathop{max}\limits_{i} (x_i) ∣∣x=imax(xi),always admissible
  • Octile distance: 基于8个方向的直线移动和对角线移动的最短路径进行计算。具体而言,Octile距离考虑了水平、垂直和对角线方向的移动。在直角移动(水平或垂直)时,距离为1;在对角线移动时,距离为根号2(即1.414)。这样设计是为了模拟在规定的移动方向上的最短路径。在路径规划算法(如A*算法)中,Octile距离经常用于启发式估计,以帮助算法找到最优路径。

【深蓝学院】移动机器人运动规划--第2章 基于搜索的路径规划--笔记,motion planning,笔记,Robotics,motion planning
上例说明A*有了贪心算法的对于目标的引导性。

4.3 A*的改进

f f f中引入 h h h的结果可知,h的引入也引入了贪心算法的特性:强目的性,faster。如果对h赋予权值则可以改变该引入特性的比重,于是出现了weighted A*,给h增减权重 ϵ ( ϵ > = 0 ) \epsilon(\epsilon>=0) ϵ(ϵ>=0),即 f = g + ϵ h f=g+\epsilon h f=g+ϵh

  • ϵ > 1 \epsilon>1 ϵ>1时,贪心占比大,算法强suboptimal,faster; ϵ = + ∞ \epsilon=+\infty ϵ=+时,忽略 g g g,算法退化为贪心算法
  • ϵ = 1 \epsilon=1 ϵ=1时,为正常A*,solution suboptimal
  • 0 < ϵ < 1 0<\epsilon<1 0<ϵ<1时,Dijkstra占比大,更接近optimal,slower;极端情况 ϵ = 0 \epsilon=0 ϵ=0退化为Dijkstra算法,solution optimal

weighted A*改进的点:

  1. ϵ > 1 \epsilon>1 ϵ>1实际上是使用solution的optimality来换取speed,速度提升是A*的数量级等级(几十倍等级别)
  2. 学界已证明weighted A*的 ϵ \epsilon ϵ-suboptimal,即 c o s t ( s o l u t i o n ) ≤ ϵ ∗ c o s t ( o p t i m a l   c o s t ) cost(solution)\leq\epsilon*cost(optimal \ cost) cost(solution)ϵcost(optimal cost)

【深蓝学院】移动机器人运动规划--第2章 基于搜索的路径规划--笔记,motion planning,笔记,Robotics,motion planning
还有weight A的改进Anytime A,ARA*,D*等研究,本课程不做介绍,可自行拓展。

更改权值的对比:

【深蓝学院】移动机器人运动规划--第2章 基于搜索的路径规划--笔记,motion planning,笔记,Robotics,motion planning
该网页可以调参进行对比: http://qiao.github.io/PathFinding.js/visual/

以下是我的实验结果:

Algorithm Length Time(ms) Operations
Best-First-Search(a=0,b=1) 29.56 1200 340
weightedA*(a=1,b=5) 27.07 17000 370
weighted A*(a=1,b=1) 26.24 13000 495
Dijkstra(a=1,b=0) 26.24 42000 2670

可以看出贪心算法operation最少,耗时最短,但solution为suboptimal(path较长),Weight A*(a=1,b=1)和Dijkstra的solution为optimal,但Weight A*(a=1,b=1)明显耗时更少,此实验中耗时提升了2.23倍,大规模问题上提升应该会更大。

【深蓝学院】移动机器人运动规划--第2章 基于搜索的路径规划--笔记,motion planning,笔记,Robotics,motion planning

【深蓝学院】移动机器人运动规划--第2章 基于搜索的路径规划--笔记,motion planning,笔记,Robotics,motion planning

【深蓝学院】移动机器人运动规划--第2章 基于搜索的路径规划--笔记,motion planning,笔记,Robotics,motion planning

【深蓝学院】移动机器人运动规划--第2章 基于搜索的路径规划--笔记,motion planning,笔记,Robotics,motion planning

5. Engineering considerations

工程实现对于算法性能影响可能有10倍,100倍都不止。

5.1 地图表示

以Occupancy grid map为例:
【深蓝学院】移动机器人运动规划--第2章 基于搜索的路径规划--笔记,motion planning,笔记,Robotics,motion planning
2Dgrid-map的表示,8连通( 2 3 − 1 2^3-1 231),3D为26连通( 3 3 − 1 3^3-1 331)

数据结构在搜索过程中其实就是在找到该节点的相邻节点时需要用到。

【深蓝学院】移动机器人运动规划--第2章 基于搜索的路径规划--笔记,motion planning,笔记,Robotics,motion planning
推荐使用stl中的priority_queuemultimap,对vector排序可以使用make_heap方法。(VINS-MONO中用unordered_map较多)。

5.2 the best heuristic

前面降到可以使用Euclidean distance作为heuristic,尽管Euclidean distance满足 h ( n ) ≤ h ∗ ( n ) h(n)\leq h^*(n) h(n)h(n)即可找到optimal solution,但是在搜索过程中会扩展很多不必要的节点, h ( n ) ≤ h ∗ ( n ) h(n)\leq h^*(n) h(n)h(n)小于的非常多,即Euclidean distance不够tight
【深蓝学院】移动机器人运动规划--第2章 基于搜索的路径规划--笔记,motion planning,笔记,Robotics,motion planning
对于结构化的地图和结构化的移动rule,在2D情况下可以推导出任何一个节点到终点的heuristic的estimate,可直接用作我们的heuristic,我们称之为Diagonal Heuristic(对角Heuristic)

【深蓝学院】移动机器人运动规划--第2章 基于搜索的路径规划--笔记,motion planning,笔记,Robotics,motion planning

TODO:这个2D Heuristic estimate结果怎么推出来的?

上例中DIagonal Heuristic和L2 Heuristic的solution path的cost(即f)相同,即出现了路径对称性问题,因为在计算f时他们之间没有difference,于是引入了Tie breaker。

5.3 Tie breaker

直观理解是打破等号。

Tie breaker用于打破5.2上述的对称性问题,核心思想是 在cost相同的path中找到preference

目的是减少不必要的node的拓展,提高搜索效率。
【深蓝学院】移动机器人运动规划--第2章 基于搜索的路径规划--笔记,motion planning,笔记,Robotics,motion planning

【深蓝学院】移动机器人运动规划--第2章 基于搜索的路径规划--笔记,motion planning,笔记,Robotics,motion planning

  • 方法1:在计算Heuristic时加入一个系数 p = 一步的最小 c o s t 可能的 p a t h 的最大 c o s t ( 比如矩形地图的斜对角线 c o s t ) p=\frac{一步的最小cost}{可能的path的最大cost(比如矩形地图的斜对角线cost)} p=可能的path的最大cost(比如矩形地图的斜对角线cost)一步的最小cost这里还不是很理解为什么加入一个 p p p就能使f不同,需要结合代码具体理解。
    这样会轻微打破admissible条件,因为h有小幅的增大,admissible heuristic取等号时是在没有任何障碍物情况下,而实际工程中由于存在较多obstacle,计算出来的h通常不会达到tight heuristic。

  • 方法2:定义rule:当f相同时,取h更小的。

  • 方法3:在f或者g上加一个deterministic random numbers(提前确定好的随机数,确定之后不能变,使用hash映射),工程实现可能较复杂,但效果会比前面的好。

  • 方法4:倾向于走直线,同样是slightly change heuristic,给heuristic加上一个corss,让其更倾向走符合直观感受的对角线path。

还有很多其他方法,可以看论文。

但是Tie breaker也会带来一些负面影响,我们最终给到robotic的是一条可执行的轨迹trajectory,trajectory是由我们的规划出的path来生成的,会涉及到traj光滑的处理,如下图,当我们使用Tie breaker在有obsacle的情况下生成了一条path,理想的trajectory是如图所示的红色光滑曲线,使用tie breaker生成了虚线所示的path,在trajectory generation过程中就比较难得到红色光滑traj,反而是矩形的path更易得到光滑traj,所以使用什么tie breaker是有讲究的,针对这种情况,引入了本章的第3块内容:JPS。
【深蓝学院】移动机器人运动规划--第2章 基于搜索的路径规划--笔记,motion planning,笔记,Robotics,motion planning

6. JPS(Jump Point Search)

JPS是一种系统性的打破路径平衡性的图搜索方法,其core idea是找到对称性并打破它
【深蓝学院】移动机器人运动规划--第2章 基于搜索的路径规划--笔记,motion planning,笔记,Robotics,motion planning

6.1 look ahead rule(pruning rule)

【深蓝学院】移动机器人运动规划--第2章 基于搜索的路径规划--笔记,motion planning,笔记,Robotics,motion planning

Look ahead rule,以例子来介绍这样一个规则:

  1. 对于无障碍物,straight到达儿子节点的情况:

从某点(4)到达另一点(1),不需要经过儿子节点(x)时的path cost为 f A f_A fA,经过儿子节点的path cost为 f B f_B fB,则
- 当 f B < f A f_{B}<f_{A} fB<fA时,才考虑从儿子节点到达该节点,称该点为natural neighbors;
- 当 f B ≥ f A f_{B}\geq f_{A} fBfA,不考虑从x到达该节点(即neighbor pruning,discard),称该节点为inferior neighbors(劣性节点)。

按照上述定义, ( f B = f 4 → x → 1 = 1 + 2 ) > ( f A = f 4 → 1 = 1 ) (f_{B}=f_{4\to x \to 1}=1+\sqrt{2}) > (f_A = f_{4\to1}=1) (fB=f4x1=1+2 )>(fA=f41=1)
所以扩展儿子节点 x x x时不考虑节点1;

从4走到3是否需要经过x:
( f B = f 4 → x → 3 = 1 + 2 ) = ( f A = f 4 → 2 → 3 = 2 + 1 ) (f_{B}=f_{4\to x \to 3}=1+\sqrt{2}) = (f_A = f_{4\to2\to3}=\sqrt{2}+1) (fB=f4x3=1+2 )=(fA=f423=2 +1)相等,所以不考虑节点3;

同理1,2,3,6,7,8均不需要考虑,只需要考虑5。

  1. 对于无障碍物,diagonal对角线到达儿子节点的情况,rule稍微有些改动:
  • f B < = f A f_{B}<=f_{A} fB<=fA时,consider
  • f B > f A f_{B}>f_{A} fB>fA时,discard

eg1:到达1
( f A = f 6 → 4 → 1 = 2 ) < ( f B = f 6 → x → 1 = 2 2 ) (f_A=f_{6\to4\to1}=2)<(f_B=f_{6\to x \to 1}=2\sqrt{2}) (fA=f641=2)<(fB=f6x1=22 )故discard 1

eg2:到达2
( f A = f 6 → 4 → 2 = 2 + 1 ) = ( f B = f 6 → x → 2 = 2 + 1 ) (f_A=f_{6\to4\to2}=\sqrt{2}+1)=(f_B=f_{6\to x \to 2}=\sqrt{2}+1) (fA=f642=2 +1)=(fB=f6x2=2 +1)
相等,diagonal相等时需要consider,详细参考论文

http://users.cecs.anu.edu.au/~dharabor/data/papers/harabor-grastien-aaai11.pdf Equation 1/2

  1. 有障碍物,straight时,3号节点必须被考虑,称为forced neighbors
  2. 有障碍物,diagonal时,1号节点必须被考虑。

以上有/无障碍物的straight和diagonal情况可以涵盖所有情况,向上下左右,向左上,左下,右上,右下均类似。

6.2 Jumping rule

【深蓝学院】移动机器人运动规划--第2章 基于搜索的路径规划--笔记,motion planning,笔记,Robotics,motion planning

为方便说明,将look ahead rule标记为①~④,jumping的原则是先递归straight jump再递归diagonal jump,发现force neighbor则会递归直线recall最上面一个node(不允许折线recall)


例子1:
p ( x ) p(x) p(x)出发进行JPS扩展:

  1. 起始点使用④,绿框部分需要被consider,w为force beighbor
    【深蓝学院】移动机器人运动规划--第2章 基于搜索的路径规划--笔记,motion planning,笔记,Robotics,motion planning
  2. 在x处向上,向右运用①最终都碰到障碍物(边界也算障碍物),jump失败
  3. 直到递归diagonal jump到y时,对y向右递归straight jump到z触发了③,绿框+蓝框是consider,蓝框为force neighbor,故z为特殊节点,jump成功,递归返回到最上层发现z的节点,即y,将y加入到open list
    【深蓝学院】移动机器人运动规划--第2章 基于搜索的路径规划--笔记,motion planning,笔记,Robotics,motion planning
  4. 递归返回到x,结合第1步的图,x节点的上、右递归straight jump,以及右上递归diagonal结束,该右下的force neighbor的递归diagonal jump,w天然是x的force neighbor,所以将w加入到open list中。

至此,完成了对x节点的所有JPS扩展,将x节点加入到close list中。


例子2:
【深蓝学院】移动机器人运动规划--第2章 基于搜索的路径规划--笔记,motion planning,笔记,Robotics,motion planning
水平,竖直jump,无事发生,对角线跳一步

【深蓝学院】移动机器人运动规划--第2章 基于搜索的路径规划--笔记,motion planning,笔记,Robotics,motion planning

【深蓝学院】移动机器人运动规划--第2章 基于搜索的路径规划--笔记,motion planning,笔记,Robotics,motion planning

向右jump时发现了特殊,于是直线recall(不允许折线recall),将蓝框的点加入到open list,绿色的起点即可加入close list,退出历史舞台。


例子3:
【深蓝学院】移动机器人运动规划--第2章 基于搜索的路径规划--笔记,motion planning,笔记,Robotics,motion planning
注意,当在扩展时发现了goal,视为发现了force neighbor,要recall并加入node到open list

最终path
【深蓝学院】移动机器人运动规划--第2章 基于搜索的路径规划--笔记,motion planning,笔记,Robotics,motion planning


例子4:
【深蓝学院】移动机器人运动规划--第2章 基于搜索的路径规划--笔记,motion planning,笔记,Robotics,motion planning

6.3 Extension

3D JPS,本质上和2D JPS相同,只是3D rules更复杂一些:Sikang之前在深蓝讲过公开课,可以看看。
【深蓝学院】移动机器人运动规划--第2章 基于搜索的路径规划--笔记,motion planning,笔记,Robotics,motion planning

大多数情况下JPS比A* 更优,因为JPS能够在复杂环境中迅速找到一个个jump point,省去了中间不必要的加入openlist的搜索过程。
【深蓝学院】移动机器人运动规划--第2章 基于搜索的路径规划--笔记,motion planning,笔记,Robotics,motion planning

但是在机器人的FOV内看不到障碍物后的点,当存在大量空旷场景时,JPS为了搜索jump point,会不断地collision query,虽然对于open list的操作变少了,但是大量的collision query耗时会增加,可能不一定比A*更优。
【深蓝学院】移动机器人运动规划--第2章 基于搜索的路径规划--笔记,motion planning,笔记,Robotics,motion planning

我的实验结果:
【深蓝学院】移动机器人运动规划--第2章 基于搜索的路径规划--笔记,motion planning,笔记,Robotics,motion planning
【深蓝学院】移动机器人运动规划--第2章 基于搜索的路径规划--笔记,motion planning,笔记,Robotics,motion planning
这种情况下明显A* 更优。

6.4 JPS summary

【深蓝学院】移动机器人运动规划--第2章 基于搜索的路径规划--笔记,motion planning,笔记,Robotics,motion planning
JPS小结:

  1. look ahead rule:遵照①~④进行拓展,举一反三

  2. jumping rule:

    1. 先水平、竖直straight扩展,再diagonal扩展,
    2. 遇obstacle或map border都视为该方向上扩展失败,直至发现满足look ahead rule中的force neighbor,
    3. 直线recall到jump的起始节点(不允许折线recall),加入到open list中
    4. 当所有方向都扩展完毕之后,将source node加入close list中。
    5. 当在扩展时发现了goal,视为发现了force neighbor,要recall并加入node到open list
  3. A* 与JPS的唯一区别在于如何选取neighbors,前者选取几何neighbors,后者根据上述2条rules选取neighbors,故用在A*上的trick均可用于JPS(diagonal heuristic,Tie breaker等)

  4. JPS 和A* 都依赖的一个点是force point一定是最优路径需要经过的点,即jump point,将起点到终点过程中的所有jump points连接起来就得到了最优path,只不过JPS通过他的规则过滤掉了很多不需要拓展的点,而A* 是所有几何neighbors都拓展。(JPS的jump point和外层循环所维护的最小cost是不一样的,前者是JPS’s rules,后者是JPS和A* 的算法框架)。

  5. 在复杂环境中JPS通常博A* 更优,但远不是always更优

  6. JPS降低了对于open list的操作(修改键值,排序等),但增加了status query的次数

  7. JPS的局限性:仅仅在uniform grid map中才能使用(1,1, 2 \sqrt2 2 这类几何特征的grid map),对于更general的图搜索问题(如带权值的非grid map),A* 可以用,而JPS无法使用。

  8. 几种搜索算法的联合对比。
    BFS:单源无权有向广度优先搜索;
    Dijkstra:单源有权有向最短路径搜索;
    A*:启发式(heuristic)的Dijkstra(找neighbor nodes规则是几何的邻居,2D最多有8个,3D最多有26个)
    JPS:在A*基础上定义了找neighbor nodes的rules(Look ahead rules & Jumping rules)
    GPT-4.0今天给了我一个heuristic
    【深蓝学院】移动机器人运动规划--第2章 基于搜索的路径规划--笔记,motion planning,笔记,Robotics,motion planning文章来源地址https://www.toymoban.com/news/detail-815713.html

7. 论文推荐

  1. http://users.cecs.anu.edu.au/~dharabor/data/papers/harabor-grastien-aaai11.pdf
  2. Planning Dynamically Feasible Trajectories for Quadrotors using Safe Flight Corridors in 3-D Complex Environments, Sikang Liu, RAL 2017

到了这里,关于【深蓝学院】移动机器人运动规划--第2章 基于搜索的路径规划--笔记的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【移动机器人】基于JADE改进差分算法的多AGV路径规划

      最近帮同学做个东西,但是问题在于是之前从没接触过的领域–移动机器人轨迹规划,虽然也是搞机器人的,但是对 AGV 那边的情况是一无所知,这次能完成也算是挑战成功。此次任务目的是多辆AGV小车搬运货物,保证搬运总时间最短并且小车与货物之间,小车与小车之

    2024年02月10日
    浏览(48)
  • 动态规划学习——机器人运动

    问题: 一共有N个位置,机器人从start开始,走K步到end 机器人到1后只能向2运动,到N后只能向N-1运动,即不能越界,只能在1-N的位置运动 求总的路线的个数 例: N=4,startp=1,endp=3,K=4 则路线如下: 1-2-3-4-3 1-2-3-2-3 1-2-1-2-3 总共有3条路线 参考资料: bilibili 马士兵教育——左程云

    2024年01月22日
    浏览(43)
  • 六自由度机器人(机械臂)运动学建模及运动规划系列(四)——轨迹规划

    对机器人进行轨迹规划的主要任务是,根据机器人的工作环境和工作任务要求,求得一系列机器人末端位姿变换的时间序列,使得机器人末端可以正确地从初始姿态沿着期望的轨迹运动到终止位姿,完成工作任务,。对于六自由度的机器人来说,轨迹规划要解决的关键问题是

    2024年02月03日
    浏览(70)
  • 移动机器人农田机器人全覆盖路径规划

    鉴于目前网上对于全覆盖路径规划方面的资料比较少,本次博客内容主要分享下拖拉机在农田里面作业的路径规划,以及轨迹优化。 目录 1. 什么是全覆盖路径规划 2. 实用案例 3. 农田作业机器人 如何获取地图 如何规划出全覆盖的路径 如何确保规划出来的路径是符合车辆动力

    2024年01月25日
    浏览(55)
  • 【运动规划算法项目实战】如何实现机器人多目标点导航

    在ROS机器人应用中,实现机器人多目标点导航是非常常见的需求。本文将介绍如何使用ROS和actionlib来实现机器人的多目标点导航,目标点信息将被记录在YAML文件中。 我们可以通过使用MoveBaseAction来实现机器人的导航功能。MoveBaseAction是一个ROS中的action类型,它提供了控制机器

    2024年02月02日
    浏览(47)
  • 六自由度机器人(机械臂)运动学建模及运动规划系列(一)——简介

    毕业设计做了六轴机器人相关的课题,做完之后学到很多,在这里分享一下。本篇首先对六轴机器人及其研究内容进行简单的介绍。 六轴机器人中的六轴指个六自由度,由关节和连杆组成。常见的六轴机器人为 串联型旋转关节机器人 。这里以一款川崎机器人为例,展示一下

    2024年02月02日
    浏览(47)
  • 建模分析 | 差速轮式移动机器人运动学建模(附Python/Matlab仿真)

    🔥附C++/Python/Matlab全套代码🔥课程设计、毕业设计、创新竞赛必备!详细介绍全局规划(图搜索、采样法、智能算法等);局部规划(DWA、APF等);曲线优化(贝塞尔曲线、B样条曲线等)。 🚀详情:图解自动驾驶中的运动规划(Motion Planning),附几十种规划算法 差速轮式移动机器人

    2024年02月05日
    浏览(46)
  • 动态规划—机器人移动问题(Java)

    😀前言 机器人移动问题是一个经典的动态规划应用场景,它涉及到在给定范围内的位置上进行移动,并计算到达目标位置的方法数。本文将介绍三种解决这一问题的方法:暴力递归、缓存法和动态规划。通过比较不同方法的优缺点,我们将深入理解动态规划在解决问题中的

    2024年04月28日
    浏览(42)
  • 【运动规划算法项目实战】如何实现机器人多目标点导航(附ROS C++代码)

    在ROS机器人应用中,实现机器人多目标点导航是非常常见的需求。本文将介绍如何使用ROS和actionlib来实现机器人的多目标点导航,目标点信息将被记录在YAML文件中。 我们可以通过使用MoveBaseAction来实现机器人的导航功能。MoveBaseAction是一个ROS中的action类型,它提供了控制机器

    2024年02月10日
    浏览(43)
  • 基于C#的机器人仿真平台和机器人运动学算法实现

    一、平台搭建 1.利用wpf自带的库进行机器人各关节导入 相关代码段: 导入效果如图: 效果视频: 2.通过正运动学显示机器人当前位置信息 拖动机器人并且实时改变其位置信息: xaml代码部分: 算法部分:  3.功能实现(在X/Y/Z轴上设置一个移动距离,然后机器人自动移动该

    2024年02月16日
    浏览(55)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包