如何提升基于Boost Graph实现的Astar路径查找算法的运行速度

问题描述 #

我有一个基于3D环境拓扑生成的图，其定义如下：

struct VertexProperty
{
  std::uint32_t label;
  std::string name;
};

typedef float Cost;

// specify some types
typedef boost::adjacency_list<
    boost::setS,            // edge
    boost::vecS,            // vertex
    boost::undirectedS,     // type
    VertexProperty,         // vertex property
    boost::property<boost::edge_weight_t, Cost>> // edge property
  GraphT;

我通过遍历从3D环境拓扑（可视为仿真区域）得到的邻接表来填充该图，添加边的代码如下：

boost::tie(e, edge_added) = boost::add_edge(u, v, g);

到这一步为止所有操作的运行速度都处于合理区间。完成图构建后我运行Astar算法，对包含约730个顶点、1873条边的图进行处理需要耗时约11秒，这一耗时对于规模不大的图来说明显过高。我使用的是euclidean heuristic（欧氏启发函数），以及和boost-astar-cities示例一致的经典goal_visitor，Astar的调用代码如下：

try {
      auto heuristic =
        distance_heuristic<GraphT, Cost, SuperVoxelClusters *>(
        &supervoxel_clusters_, goal_vertex, g);
      auto c_visitor = custom_goal_visitor<vertex_descriptor>(goal_vertex);

        boost::astar_search_tree(
          g, start_vertex, heuristic,
        boost::predecessor_map(&p[0]).distance_map(&d[0]).visitor(c_visitor));
      

      // A path was NOT found. Warn user about it
      RCLCPP_WARN(logger_, "%s search failed to find a valid path!", graph_search_method_.c_str());
    } catch (FoundGoal found_goal) {
      // Found a path to the goal, catch the exception
      // Handle the path ...
     }

如果路径存在我可以成功找到路径，但性能问题十分突出。下方是我可视化的已构建图和路径示意图，需注意路径经过插值、平滑等后处理，外观和原始寻路输出存在差异。请问有什么方案可以将该算法的运行速度提升到合理水平？

优化方案 #

• 优化启发函数实现：当前启发函数依赖SuperVoxelClusters查询顶点坐标，每次调用的查表开销会被A*的高频调用放大。建议将每个顶点的3D坐标直接存入VertexProperty结构体，启发函数直接从顶点属性读取坐标计算距离，无需额外查表，可将启发函数调用开销降至最低。
• 调整图存储结构：当前使用boost::setS作为边的存储容器，set的有序存储特性会带来额外的遍历开销，对于静态构建完成后不会动态增删边的场景，可将boost::adjacency_list的第一个模板参数替换为boost::vecS，边遍历性能可提升3~5倍，仅需在建图时保证无重复边即可，就算需要去重，开销也远低于性能收益。
• 替换异常终止逻辑：使用抛异常的方式终止A搜索会带来极高的栈展开开销，建议将自定义visitor改为检测到目标顶点后设置终止标记，使用支持提前终止的A调用重载，完全去掉异常抛出和捕获的逻辑，这部分开销在小规模图上甚至可能占总耗时的一半以上。
• 开启编译优化：Boost图库是模板实现，高度依赖编译优化做内联展开，Debug模式下的额外边界检查、无优化编译会让性能下降10~100倍，确认使用-O2及以上优化等级编译Release版本，可获得量级性能提升。
• 预计算边权重：当前调用add_edge时没有显式传入边权重，A计算路径代价时需要动态计算边长度，建议在添加边的时候直接将两个端点的欧氏距离作为权重传入add_edge，后续A运行时直接读取边权重即可，避免重复计算。

内容的提问来源于stack exchange，提问作者fet.atas