4. 单无人系统搜索与覆盖基础方法
在多无人系统协同之前，必须先回答一个更基础的问题：单个无人系统如何独立完成一片区域的搜索与覆盖？这一节讨论四种最常用的基础方法——栅格遍历、螺旋搜索、随机搜索与贪心策略。它们既是协同算法的“单机底座”，也是理解后续多机分工、区域分配与冲突消解的前提。需要先明确一个贯穿全节的约定：设搜索区域为矩形 A，被离散为 m×n 个等尺寸栅格，每个栅格边长 L，无人系统的传感器有效探测半径记为 r，飞行速度记为 v。所有方法的目标都是让传感器扫过的区域尽可能覆盖 A，区别在于“按什么顺序走”。
一、栅格遍历：把连续空间变成可枚举的格子
栅格遍历（Grid Traversal）是最直观的方法：将区域划分为栅格后，让无人系统依次访问每个栅格中心或按“弓”字形（boustrophedon）路径逐行扫描。若采用弓字形，路径总长度约为 m·n·L 加上行间转向的额外开销，覆盖时间 T ≈ (m·n·L + 转向损耗)/v。它的最大优点是完备性：只要传感器半径 r ≥ L/2，理论上不会遗漏任何栅格；缺点是路径僵化，遇到障碍或目标概率分布不均时效率骤降。
实际实现时，栅格遍历通常配合“覆盖标记”数组：每访问一个栅格，将其标记为已覆盖，并检查是否所有栅格均已标记。若传感器半径大于栅格边长，可一次覆盖多个相邻栅格，此时应把 r 折算为“覆盖半径内的栅格集合”，避免重复访问。例如取 L=10 m、r=15 m，则一个航点可覆盖约 3×3 的栅格邻域，实际航点数可减少到原来的 1/9 左右。
二、螺旋搜索：从中心向外或由外向内的连续扩展
螺旋搜索（Spiral Search）让无人系统沿阿基米德螺线或方形螺线运动，从区域中心逐圈向外扩展（或反向收缩）。其核心参数是螺距 d，即相邻两圈之间的径向间距。为保证不漏扫，应满足 d ≤ 2r；若 d 过大，圈与圈之间会出现覆盖空洞。螺旋路径的优点是起始点明确、路径连续、转弯平滑，适合目标初始位置不确定但大致位于区域中心的场景，例如对坠落目标或信号源的搜索。
螺旋搜索的覆盖时间与区域半径 R 和螺距 d 有关，近似为 T ≈ πR²/(d·v)。当 d=2r 时达到理论最短时间，但实际中因转弯半径限制，d 往往略小于 2r。它的性能边界在于：对非中心分布的目标效率低，且一旦区域形状不是凸形，螺旋线容易被边界截断，需要额外的边界处理逻辑。
三、随机搜索：无先验信息下的概率覆盖
随机搜索（Random Search）不预设路径，而是让无人系统按随机方向或随机航点运动。它看似“低效”，但在目标位置完全未知、且区域内有障碍时，随机策略反而具有鲁棒性：不会因某条固定路径被阻断而整体失效。随机搜索的覆盖性能通常用“发现概率”描述：若目标在区域内均匀分布，经过时间 t 后，期望覆盖率约为 1 − e^(−k·v·t/A)，其中 k 为与传感器宽度相关的系数。
随机搜索的关键不是“完全随机”，而是带约束的随机：例如限制转向角、避免原地打转、记录已访问区域并降低重复访问概率。常见实现是“随机航点+避障”：在未覆盖栅格中随机抽取一个作为下一目标点，用直线或简单避障路径飞过去，到达后再抽下一个。这样既保留随机性，又逐步逼近全覆盖。
四、贪心策略：每一步都选“当前最优”
贪心策略（Greedy Strategy）在每一步选择“当前看起来收益最大”的动作。在覆盖问题中，典型贪心规则是：从当前位置出发，选择能覆盖最多未覆盖栅格、且飞行代价最小的下一个航点。其评价函数可写为 score = α·新增覆盖数 − β·飞行距离，其中 α、β 为权重。贪心策略计算量小、响应快，适合在线执行；但它不保证全局最优，容易陷入“局部最优陷阱”——例如为了贪图眼前一大片未覆盖区，而绕远路，导致后续路径碎片化。
一个实用的改进是“贪心+回退”：当贪心选择的航点导致剩余未覆盖区域被分割成多个孤立小块时，暂停贪心，先处理最近的小块，再回到主区域。这样能在保持低计算量的同时，明显减少总航程。
五、四种方法的性能边界与选择依据
把四种方法放在同一坐标系下比较，可以归纳出三条边界：第一，完备性与效率的权衡。栅格遍历和螺旋搜索在参数正确时能保证覆盖，但路径固定、对障碍和先验分布不敏感；随机搜索和贪心策略更灵活，但只能给出概率或局部保证。第二，先验信息的价值。若已知目标大致在中心，螺旋搜索最优；若目标均匀分布且无障碍，栅格遍历最稳；若目标位置完全未知且环境复杂，随机搜索更鲁棒；若需要在线快速响应，贪心策略最合适。第三，参数敏感性。螺旋搜索对螺距 d 极敏感，d 超过 2r 会直接漏扫；栅格遍历对栅格边长 L 敏感，L 过大则覆盖空洞，过小则航程激增；贪心策略对权重 α、β 敏感，权重失衡会导致绕路或覆盖碎片化。
六、一个可复现的示例：同一区域下的四种路径对比
设区域为 100 m × 80 m，栅格边长 L=10 m，传感器半径 r=8 m，速度 v=5 m/s。按上述参数：
- 栅格遍历：栅格数 10×8=80，弓字形路径约 80×10=800 m，加转向损耗约 860 m，T≈172 s。
- 螺旋搜索：取螺距 d=2r=16 m，区域等效半径约 50 m，路径长约 π×50²/16≈491 m，T≈98 s，但仅当目标靠近中心时有效。
- 随机搜索：若 k≈0.6，则 100 s 后期望覆盖率约 1−e^(−0.6×5×100/8000)≈1−e^(−0.375)≈31%，远低于前两者，但障碍场景下不会完全失效。
- 贪心策略：取 α=1、β=0.02，单步新增覆盖约 3 个栅格、飞行约 15 m，score≈3−0.3=2.7；若某步新增覆盖仅 1 个但飞行 40 m，score≈1−0.8=0.2，贪心会优先选前者。实际航程通常介于栅格遍历与螺旋之间，约 600～750 m。
这组数字说明：没有一种方法在所有场景下都最优。栅格遍历胜在稳定，螺旋搜索胜在中心先验，随机搜索胜在鲁棒，贪心策略胜在灵活。多无人系统协同搜索的第一步，往往就是根据任务先验和环境复杂度，为每台无人系统选择合适的基础方法，再通过区域划分和路径协调，把单机能力组合成整体覆盖能力。