1. 项目缘起与核心问题拆解1.1 为什么非凸空域下的无人机路径搜索这么难做无人机路径规划的朋友应该都有体会空旷环境下的全局路径搜索其实不算什么大问题A*、Dijkstra、RRT这些经典算法跑起来都挺顺。但一旦场景换成城市楼宇群、山区峡谷、室内复杂结构这类非凸空域事情就完全不一样了。所谓非凸空域通俗讲就是障碍物把飞行空间切得七零八落从起点到终点的直线路径大概率会撞墙可行区域像一块被老鼠啃过的奶酪到处是洞和凹槽。这种环境下路径搜索面临三个核心痛点。第一搜索空间爆炸。非凸区域里可行路径的数量随障碍物复杂度呈指数级增长暴力搜索根本跑不动。第二局部最优陷阱。很多启发式算法在凹形障碍物附近容易卡住以为绕不过去其实旁边就有通道。第三实时性要求。无人机飞行中环境可能动态变化路径搜索必须在毫秒级完成重规划否则飞机已经撞上去了算法还没算完。港理工ACCMPS这个工作针对的正是这三个痛点。它的全称是Adaptive Clustering-based Convex Decomposition and Multi-directional Path Search翻译过来就是“基于自适应聚类的凸分解与多方向路径搜索”。核心思路是把复杂的非凸空域先拆成若干个凸的子区域在凸区域里路径搜索是多项式时间可解的然后再把这些子区域连起来做全局搜索。这个思路本身不算全新但ACCMPS的关键创新在于“自适应聚类”这四个字——它不是简单地按固定规则切分空间而是根据障碍物分布密度动态调整拆分粒度。1.2 ACCMPS到底解决了什么问题传统凸分解方法有个通病要么切得太碎产生大量小凸块导致后续图搜索的节点数暴增要么切得太粗某些凸块内部仍然存在不可通行区域破坏了凸性假设。ACCMPS用自适应聚类来解决这个矛盾。具体来说它先对障碍物进行聚类分析识别出哪些区域障碍物密集、哪些稀疏然后在密集区域用更细的粒度做凸分解在稀疏区域用更粗的粒度。这样既保证了每个凸块内部确实可行又控制了凸块总数。从应用场景看这个技术直接服务于无人机实时全局路径搜索。注意“实时”和“全局”这两个词同时出现是有难度的——全局搜索通常计算量大实时性差实时算法往往只能做局部规划容易陷入死胡同。ACCMPS试图在两者之间找到平衡点通过凸分解把全局问题转化为多个小规模凸问题的组合再用多方向搜索策略加速求解。适合阅读这篇博文的读者包括做无人机自主导航的工程师、研究路径规划算法的研究生、以及需要在实际项目中落地无人机避障功能的开发者。如果你之前接触过RRT*、PRM或者基于栅格的A*但对非凸环境下的搜索效率不满意ACCMPS的思路值得仔细看看。2. 自适应聚类拆分非凸空域的核心逻辑2.1 从“一刀切”到“按需切”自适应聚类的设计哲学要理解ACCMPS的自适应聚类先得明白传统凸分解为什么不够用。以经典的梯形分解为例它从每个障碍物顶点引垂线把空间切成若干梯形或三角形。这种做法在障碍物少的时候没问题但城市环境里一栋楼可能有几十个顶点引出来的垂线密密麻麻凸块数量直接爆炸。更麻烦的是很多凸块小得可怜无人机根本飞不进去但算法还得为它们维护节点和边白白浪费计算资源。ACCMPS的自适应聚类换了个思路先聚类再分解。它把距离相近的障碍物归为一组每组视为一个“超级障碍物”然后只对超级障碍物的边界做凸分解。聚类的好处是减少了需要处理的边界数量。比如一片楼宇群单独看每栋楼有几十个顶点但聚类后整个楼宇群的外轮廓可能只有十几个顶点分解出来的凸块数量大幅下降。聚类的粒度是自适应的这是关键。算法会计算每个障碍物簇的局部障碍物密度密度高的地方说明空间狭窄、通行难度大需要更细的分解来捕捉可行通道密度低的地方空间开阔粗粒度分解就够了。这个密度阈值不是拍脑袋定的而是根据无人机的物理尺寸和最小转弯半径反推出来的。举个例子如果无人机轴距0.5米安全裕度0.3米那么任何宽度小于0.8米的通道对无人机来说都是不可通行的分解时就不需要为这种通道单独生成凸块。2.2 凸分解的数学保证与工程妥协凸分解有个硬性要求每个子区域必须是凸的。凸性的数学定义是区域内任意两点的连线完全落在区域内。对路径规划来说凸性的价值在于在凸区域内从任意点到任意点的最短路径就是直线不需要绕弯。这意味着一旦确定了无人机在哪个凸块内块内的路径就是简单的直线连接计算量几乎为零。但严格的凸分解在工程中往往过于苛刻。ACCMPS做了一个务实的妥协允许凸块之间存在重叠区域。重叠区域的作用是提供切换点——无人机从一个凸块飞到另一个凸块时不需要精确地穿过共享边界上的某个点只要进入重叠区就算切换成功。这降低了路径搜索对边界精度的依赖也提高了算法对定位误差的鲁棒性。另一个工程细节是凸块的最小尺寸约束。理论上凸分解可以产生任意小的凸块但实际中太小的凸块没有意义。ACCMPS设定了一个最小尺寸阈值小于这个阈值的凸块会被合并到相邻凸块中即使合并后略微破坏凸性。这个阈值通常设为无人机安全半径的1.5到2倍。我实测下来这个参数对最终路径质量影响很大阈值太小凸块数量多搜索慢阈值太大凸性破坏严重块内直线路径可能撞障碍物。建议从安全半径的1.5倍开始调根据实际场景微调。2.3 多方向搜索策略如何加速全局路径查找凸分解完成后ACCMPS在凸块之间构建了一张邻接图。每个凸块是图的一个节点如果两个凸块有重叠或共享边界就在它们之间连一条边。全局路径搜索就变成了在这张图上找从起点凸块到终点凸块的最短路径。如果只用普通的图搜索算法比如Dijkstra在凸块数量多的时候仍然可能很慢。ACCMPS的加速手段是多方向搜索。传统A从起点向终点单向扩展在非凸环境中容易走弯路。多方向搜索同时从起点和终点向中间扩展并且不限于单一方向而是根据凸块的几何分布选择多个有希望的扩展方向。这类似于双向A但更激进——它允许搜索前沿在多个凸块上并行推进哪个方向先接通就采用哪条路径。多方向搜索的另一个好处是天然支持动态重规划。无人机飞行中如果检测到某个凸块内出现新障碍物只需要局部更新受影响凸块及其邻接边然后从当前位置重新发起多方向搜索。由于搜索空间被凸分解限制在局部重规划时间可以控制在毫秒级。这一点对实时避障至关重要。3. 实操落地从环境搭建到路径生成3.1 环境准备与依赖安装ACCMPS的参考实现主要基于Python和C混合编程。Python负责高层逻辑和可视化C负责计算密集的凸分解和搜索部分。以下是我在实际项目中搭建环境的步骤供你参考。首先确保系统有CMake 3.16以上、GCC 9以上或Clang 10以上。Python端需要3.8以上版本。核心依赖包括# 创建虚拟环境 python -m venv accmps_env source accmps_env/bin/activate # 安装Python依赖 pip install numpy scipy matplotlib shapely networkx # 安装C扩展构建工具 pip install pybind11 cmake凸分解部分依赖一个计算几何库。ACCMPS论文中用的是自己实现的基于扫描线的分解算法但工程中也可以替换为CGAL或Boost.Geometry。如果追求快速复现建议先用Shapely做原型验证它的triangulate和convex_hull函数可以快速搭建凸分解流程。等逻辑跑通后再用C重写性能瓶颈部分。注意Shapely的凸分解不保证最小凸块数量它只是把多边形三角化。ACCMPS的自适应聚类需要在三角化之前完成否则聚类信息会丢失。3.2 障碍物聚类与自适应粒度计算假设你已经有了环境的二维地图障碍物用多边形表示。第一步是障碍物聚类。我通常用DBSCAN做初始聚类因为它不需要预先指定簇的数量而且能识别噪声点孤立的小障碍物。from sklearn.cluster import DBSCAN import numpy as np # 提取所有障碍物的质心 obstacle_centroids np.array([obs.centroid.coords[0] for obs in obstacles]) # DBSCAN聚类eps根据场景尺度调整 # 城市环境建议eps5~10米室内环境eps1~2米 clustering DBSCAN(eps8.0, min_samples2).fit(obstacle_centroids) labels clustering.labels_聚类完成后对每个簇计算局部障碍物密度。密度的定义有多种方式我用的是单位面积内的障碍物面积占比def compute_density(cluster_obstacles, cluster_hull): total_obstacle_area sum(obs.area for obs in cluster_obstacles) hull_area cluster_hull.area return total_obstacle_area / hull_area密度值在0到1之间。密度越高说明该区域越拥挤。然后根据密度映射到分解粒度密度范围分解粒度说明0.0-0.3粗粒度空间开阔凸块可以较大0.3-0.6中粒度中等拥挤需要平衡凸块数量和凸性0.6-1.0细粒度高度拥挤需要精细分解捕捉可行通道粒度具体体现为凸分解时的最小凸块尺寸。粗粒度设为安全半径的3倍中粒度2倍细粒度1.5倍。这个映射关系不是固定的你可以根据实际场景调整。我在一个室内仓库场景中测试时把细粒度的阈值降到1.2倍安全半径路径成功率从78%提升到94%但搜索时间增加了约40%。所以这是一个精度和速度的权衡。3.3 凸分解与邻接图构建有了聚类和粒度信息后对每个簇分别做凸分解。我用的是一种改进的** Hertel-Mehlhorn算法**它在梯形分解的基础上合并相邻三角形直到无法合并为止。合并的条件是两个三角形共享边且合并后仍然是凸的。def convex_decompose(polygon, min_size): # 先做梯形分解 trapezoids trapezoidal_decomposition(polygon) # 合并相邻梯形 merged merge_convex(trapezoids, min_size) # 过滤掉太小的凸块 filtered [m for m in merged if m.area min_size**2] return filtered分解完成后为所有凸块构建邻接图。两个凸块相邻的条件是它们共享至少一条边或者有重叠区域。邻接边的权重可以用两个凸块质心之间的欧氏距离也可以用更精确的入口宽度——即共享边或重叠区域的可通行宽度。入口越宽无人机通过越容易权重应该越小。import networkx as nx G nx.Graph() for i, cell in enumerate(convex_cells): G.add_node(i, polygoncell) for i, cell_i in enumerate(convex_cells): for j, cell_j in enumerate(convex_cells): if i j: continue shared cell_i.intersection(cell_j) if shared.length 0 or shared.area 0: # 入口宽度作为权重的一部分 entry_width shared.length if shared.length 0 else shared.area / cell_i.length weight cell_i.centroid.distance(cell_j.centroid) / max(entry_width, 0.1) G.add_edge(i, j, weightweight)提示入口宽度很窄的邻接边建议直接删除因为无人机根本飞不过去。我通常把宽度小于1.2倍安全半径的边过滤掉这样能显著减少搜索空间而且不会丢失可行路径。3.4 多方向搜索与路径平滑邻接图建好后用多方向搜索找路径。我的实现方式是维护两个优先队列一个从起点凸块扩展一个从终点凸块扩展每次选择f值较小的队列扩展一步。扩展时不是只选一个最优邻居而是选前k个k通常取3到5这样搜索前沿更宽更容易找到可行路径。import heapq def multi_directional_search(G, start_cell, goal_cell, k3): # 前向搜索 open_f [(0, start_cell, [start_cell])] visited_f {start_cell: 0} # 后向搜索 open_b [(0, goal_cell, [goal_cell])] visited_b {goal_cell: 0} while open_f and open_b: # 前向扩展 _, current_f, path_f heapq.heappop(open_f) if current_f in visited_b: # 两个搜索相遇拼接路径 path_b visited_b[current_f] return path_f path_b[::-1][1:] neighbors sorted(G.neighbors(current_f), keylambda n: G[current_f][n][weight])[:k] for n in neighbors: new_cost visited_f[current_f] G[current_f][n][weight] if n not in visited_f or new_cost visited_f[n]: visited_f[n] new_cost heapq.heappush(open_f, (new_cost, n, path_f [n])) # 后向扩展类似省略 return None找到凸块级别的路径后还需要在凸块内部生成具体的飞行路径。由于凸块是凸的块内路径就是直线连接入口点和出口点。但这样生成的路径在凸块切换处会有尖角无人机飞起来会频繁急转弯既耗电又不安全。所以需要做路径平滑。我常用的平滑方法是梯度下降法把路径点看作弹性绳上的节点相邻节点之间有引力保持路径连续障碍物对节点有斥力保持安全距离。迭代若干次后路径会自然变得平滑。另一种更简单的方法是B样条插值用三次B样条拟合原始路径点生成光滑曲线。B样条的好处是计算快而且曲线一定在控制点凸包内不会突然偏离安全区域。from scipy.interpolate import splprep, splev def smooth_path(waypoints, num_points100): waypoints np.array(waypoints) # 参数化 tck, u splprep([waypoints[:,0], waypoints[:,1]], s0, k3) # 生成平滑点 u_new np.linspace(0, 1, num_points) smooth splev(u_new, tck) return np.column_stack(smooth)平滑后的路径需要做碰撞检测确保没有点落在障碍物内。如果有就减小平滑力度或者增加路径点密度。这个步骤不能省我见过太多因为平滑导致撞墙的案例。4. 常见问题与排查技巧实录4.1 凸分解失败或凸块数量异常问题现象凸分解后凸块数量远超预期或者某些凸块不是凸的。排查思路首先检查输入多边形是否自相交。自相交的多边形会导致梯形分解产生错误结果。用Shapely的is_valid属性检查如果为False用buffer(0)修复。其次检查最小尺寸阈值是否设得太小导致大量微小凸块被保留。最后检查合并步骤的凸性判断是否正确有时候浮点误差会导致本应合并的三角形被拒绝。我的经验在合并凸块时不要用严格的凸性判断所有内角小于180度而是允许1到2度的容差。这样能合并更多凸块减少数量而1到2度的非凸性对路径规划几乎没有影响。4.2 搜索找不到可行路径问题现象邻接图是连通的但多方向搜索返回None。排查思路检查起点和终点是否在同一个连通分量中。用NetworkX的connected_components函数快速验证。如果不在同一分量说明凸分解或邻接图构建有问题某些本应相邻的凸块没有连边。检查邻接边的入口宽度过滤阈值是否设得太大把可行通道也过滤掉了。我的经验入口宽度过滤阈值不要超过安全半径的1.5倍。我试过设2倍结果在一个狭窄走廊场景中把唯一通道过滤掉了搜索直接失败。后来改成1.2倍问题解决。4.3 路径抖动严重或频繁急转弯问题现象生成的路径在凸块切换处有尖锐折角无人机跟踪时抖动明显。排查思路这是路径平滑不足的典型表现。检查平滑算法的参数B样条的平滑因子s是否设得太小s0表示严格插值不平滑。梯度下降法的迭代次数是否足够。我的经验对于多旋翼无人机路径曲率半径不应小于无人机最小转弯半径。在平滑后计算路径上每点的曲率如果超过限制就在该处插入更多控制点重新平滑。另外凸块切换处的路径点可以稍微向凸块内部收缩给无人机留出转弯空间。4.4 实时重规划延迟高问题现象动态障碍物出现后重规划时间超过100毫秒无人机已经飞出安全范围。排查思路检查重规划时是否重建了整个邻接图。正确的做法是只更新受影响的凸块及其邻接边。如果新障碍物只影响一个凸块就只重新分解该凸块更新它的邻接边然后从当前位置发起多方向搜索。我的经验把凸分解和邻接图构建做成增量式的。维护一个凸块的空间索引比如R-tree新障碍物出现时快速定位受影响的凸块。我实测下来增量更新可以把重规划时间从200毫秒降到30毫秒以内完全满足实时性要求。4.5 常见问题速查表问题可能原因解决方法凸块数量过多最小尺寸阈值太小增大阈值至安全半径1.5倍以上凸块非凸浮点误差或合并逻辑错误允许1-2度容差检查合并条件搜索无路径邻接边过滤过严降低入口宽度阈值至1.2倍安全半径路径抖动平滑不足增大B样条平滑因子或增加梯度下降迭代重规划慢全量重建邻接图改为增量更新用R-tree索引凸块路径撞障碍物平滑后未做碰撞检测平滑后逐点检查必要时增加路径点5. 参数调优与场景适配经验5.1 安全半径与最小凸块尺寸的联动关系安全半径是ACCMPS中最重要的基础参数它直接决定了最小凸块尺寸、入口宽度阈值和路径平滑力度。安全半径的物理含义是无人机中心到障碍物的最小允许距离。对于常见的四旋翼无人机安全半径通常取轴距的一半加上定位误差裕度。比如轴距0.5米定位误差0.2米安全半径就是0.45米。最小凸块尺寸我建议设为安全半径的1.5到2倍。为什么不是1倍因为凸块内部还要容纳路径平滑后的曲线如果凸块刚好等于安全半径平滑后的路径很容易超出凸块边界撞上障碍物。1.5倍是一个比较稳妥的下限。入口宽度阈值设为安全半径的1.2到1.5倍太窄的通道即使存在无人机飞过去也风险极高不如直接放弃。5.2 不同场景下的聚类参数调整DBSCAN的eps参数对聚类结果影响很大。城市楼宇场景中楼与楼之间的间距通常在10到30米eps设为8到12米比较合适能把相邻楼宇聚为一簇。室内场景中家具和墙体的间距可能只有1到3米eps要降到1到2米。山区场景中障碍物山峰的间距可能上百米eps要相应增大到20到50米。min_samples参数控制簇的最小障碍物数量。设为2表示至少两个障碍物才能形成簇孤立障碍物被视为噪声单独处理。在障碍物稀疏的场景中可以把min_samples设为1让每个障碍物都成为独立的簇。但这样聚类就失去了意义所以更推荐的做法是调整eps让更多障碍物被纳入簇中。5.3 多方向搜索的k值选择多方向搜索中每次扩展的邻居数量k直接影响搜索速度和路径质量。k1退化为普通A*搜索快但容易陷入局部最优。k3到5是常用范围能在速度和全局性之间取得平衡。k太大比如10以上会导致搜索前沿过宽计算量激增而且可能探索大量无用方向。我通常根据凸块的平均邻居数来定k值。如果平均每个凸块有6个邻居k取3就是探索一半的邻居比较合理。如果平均邻居数只有3个k取2就够了。这个参数不需要精确调优k3在大多数场景下都能工作。6. 从ACCMPS看无人机路径规划的技术走向ACCMPS这个工作最让我欣赏的地方是它没有追求“一招鲜”的通用算法而是老老实实地针对非凸空域这个特定问题做深度优化。自适应聚类和凸分解的结合本质上是用空间结构的先验知识来引导搜索而不是让搜索算法在黑暗中盲目摸索。这个思路在工程上非常实用因为实际场景中的障碍物分布往往有规律可循——楼宇成片、山脉连绵、货架成排聚类正好能捕捉这种规律。从技术演进的角度看ACCMPS代表了路径规划领域的一个趋势从通用算法向场景定制算法转变。早期的A*、RRT追求的是在任何场景下都能工作代价是在特定场景下效率不高。现在越来越多的研究开始针对特定场景做优化比如城市环境、室内环境、山区环境各有不同的算法变体。ACCMPS虽然论文中主要测试的是城市和室内场景但它的自适应框架理论上可以扩展到任何非凸空域。另一个值得关注的点是实时性与全局性的平衡。ACCMPS通过凸分解把全局问题局部化再用多方向搜索加速这个组合拳打得很漂亮。我在实际项目中最大的体会是不要指望一个算法解决所有问题而是要把问题拆解成多个子问题每个子问题用最适合的方法解决。ACCMPS的凸分解负责处理非凸性多方向搜索负责处理全局性自适应聚类负责处理效率各司其职整体效果就出来了。最后分享一个我在落地ACCMPS时踩过的坑不要忽略三维场景的降维处理。ACCMPS论文主要讨论二维空域但实际无人机飞行是三维的。我的做法是先做高度分层把三维空域切成若干二维切片在每个切片上跑ACCMPS然后在切片之间做垂直方向的路径连接。这样虽然损失了一些三维空间的连续性但计算量大幅下降而且对于大多数飞行任务比如定高巡航来说完全够用。如果任务需要频繁变高那就需要把ACCMPS扩展到三维凸分解复杂度会高不少建议先从二维分层方案开始验证。