Routing是全局路径规划，类似“高德导航”。通过使用路由地图routing_map，输入是2点间的所有路段。

导航器navigator

1，navigator是路由搜索的实施类，搜索具体路径。

2，首先，构造时候，加载routing_map的routing地图；然后，整合routing地图得到TopoGraph

拓扑图Topograph

1,routing模块使用细节丰富的拓扑图Topograph循迹

1. Topograph来源于Graph,加工原始的点和边信息，提供了额外的数据结构
2. 通过topograph，首先，查询一个道路IDLane ID对应的TopoNode,然后，找到TopoNode的相邻边和node。例如，拓扑点TopoNode A（对应道路Lane A）有一条类型为LEFT的OutEdge链接到TopoNode B(Lane B)表示lane A 的左就是lane B。

Routing搜索流程

1. 获取waypoints所在的Lane对应的TopoNode
2. 添加黑名单
3. 依次搜索前后两个航点的路径，然后，拼接这个路径
4. 路径搜索的输出格式是RoutingResponse

拓扑子图SubTopoGraph

1. 由于在拓扑图topograph的拓扑点TopoNode之间，带有黑名单Lanesegment,不能使用，引入拓扑子图SubTopoGraph来解决问题，选择能通行路段。要用优化后LaneSegment，从重建TopoEdge,到重建TopoGraph。

2，创建拓扑子图SubTopoGraph时候，

1，a*算法原理和伪代码

A*算法

算法有个主循环，重复地从openlist中拿出最优节点（f值最小）。如果n不是目标节点，删除openlist的n,并添加到closedlist，查看n的所有邻接点n’。如果邻接点n’在closedlist中，表明邻居n’已被检查过，则无需再检查（*）；如果n’在openlist中，无需再检查（*）。否则，把该邻接点n’加入openlist，把该邻接点n’的父节点设置为n，到达 n’的开销g(n’)=g(n) + movementcost(n, n’)

（*）这里我略过了一个小细节。你应当检查节点的g值，如果新计算得到的路径开销比该g值低，那么要重新打开该节点（即重新放入OPEN集）。

（解释：n’是在open表里还是在closed表里，若在closed 表中，则检查新路径是否比原先更好（f值更小cost<g(n’)），若是则采用新路径，否则把n’添加入open表）

1. 大模块（类）
   strategy.h文件

class?Strategy类：

virtual?bool?Search(const?TopoGraph* graph, const?SubTopoGraph* sub_graph,

const?TopoNode* src_node, const?TopoNode* dest_node,

std::vector<NodeWithRange>* const?result_nodes) = 0;

};

//1，TopoGraph?2，SubTopoGraph?3，起点，4，终点， 5，结果容器

a_star_strategy.h文件

class?AStarStrategy?类?

函数：

virtual?bool?Search(const?TopoGraph* graph, const?SubTopoGraph* sub_graph,

const?TopoNode* src_node, const?TopoNode* dest_node,

std::vector<NodeWithRange>* const?result_nodes);

//1，TopoGraph?2，SubTopoGraph?3，起点，4，终点， 5，结果容器

double?HeuristicCost(const?TopoNode* src_node, const?TopoNode* dest_node);

//计算启发函数

输入src_node；dest_node

输出distance

计算：?h(n)=abs(dx-nx)+abs(dy-ny)

double?GetResidualS(const?TopoNode* node);//计算从节点node到终点的剩余距离S

double?GetResidualS(const?TopoEdge* edge, const?TopoNode* to_node);//计算从边edge到edge的剩余距离S

变量：

std::unordered_set<const?TopoNode*> open_set_;

std::unordered_set<const?TopoNode*> closed_set_;

std::unordered_map<const?TopoNode*, const?TopoNode*> came_from_;//父节点

std::unordered_map<const?TopoNode*, double> g_score_;//从开始点到当前点的代价

std::unordered_map<const?TopoNode*, double> enter_s_;//每个点的进入距离

1. 小模块（实现）

struct?SearchNode?{

const?TopoNode* topo_node = nullptr;

double?f = std::numeric_limits<double>::max();

SearchNode() = default;

explicit?SearchNode(const?TopoNode* node)

: topo_node(node), f(std::numeric_limits<double>::max()) {}

SearchNode(const?SearchNode& search_node) = default;

bool?operator<(const?SearchNode& node) const?{

// in order to let the top of priority queue is the smallest one!

return?f > node.f;

}

bool?operator==(const?SearchNode& node) const?{

return?topo_node == node.topo_node;

}

};

HeuristicCost：启发代价

输入src_node；dest_node

输出distance

计算：?h(n)=abs(dx-nx)+abs(dy-ny)

GetResidualS：剩余距离

Open_set_

Closed_set_

came_from_移动代价：子：父

modules/routing/graph/topo_node.h文件：

Navigator:

1,Navigator时路由搜索的实施类,完成具体的路径搜索

参考：

百度无人驾驶apollo项目路径规划a*算法分析:

(91条消息) 百度无人驾驶apollo项目路径规划a*算法分析_lijianhua1205的博客-CSDN博客

Apollo项目Routing模块A*算法剖析

(91条消息) Apollo项目Routing模块A*算法剖析_知行合一2018的博客-CSDN博客_apollo路由算法

路径规划学习入门

(91条消息) 路径规划学习入门_沐清浅的博客-CSDN博客_路径规划

路径规划Github库推荐

(91条消息) 路径规划Github库推荐_Expected future的博客-CSDN博客_github 路径规划

Apollo3.5:基于拓扑地图TopoGraph的Routing模块A*算法路径导航（RRT）

(91条消息) Apollo3.5:基于拓扑地图TopoGraph的Routing模块A*算法路径导航_yu_明明明皓的博客-CSDN博客

混合A*算法研究

混合A*算法研究_robinvista的博客-CSDN博客_混合a星

多伦多大学Self-Driving Cars自动驾驶专项课程学习

(91条消息) 多伦多大学Self-Driving Cars自动驾驶专项课程学习_何伯特的博客-CSDN博客

机器人决策与运动规划

(91条消息) 机器人决策与运动规划_何伯特的博客-CSDN博客

Apollo Routing拓扑地图生成源码学习

(91条消息) Apollo Routing拓扑地图生成源码学习_wujiangzhu_xjtu的博客-CSDN博客_apollo hdmap源码解析