蜜蜂采蜜教会AI：BSO蜂群优化多机器人任务分配
导读：20个任务、15台AGV，怎么分？贪心算法每次选最近的会给后续埋坑，BSO用群体智能50个"蜜蜂"并行搜索100代，找到近似全局最优分配。本文拆解BSO的交叉变异逻辑，以及冲突发生时WAITING→重规划的实时化解机制。
一、BSO群体智能原理
想象一群蜜蜂要采集100朵花，它们不知道哪朵花最好蜜，会派出50只蜜蜂同时去探索。每只蜜蜂探索后会"交流经验"，慢慢找到最佳采蜜路线——这就是BSO的核心思想。
BSO (Batch Sequence Optimization) 本质上是遗传算法的蜂群版：通过模拟生物的进化过程，在大量候选方案中筛选出最优解。
一句话理解
BSO = 50只蜜蜂（候选方案）× 100代进化（迭代优化）→ 全局最优分配
核心流程图
flowchart TB
subgraph INIT["1. 随机撒网"]
P["随机生成50个候选方案<br/>（每条方案=一个分配方案）"]
end
subgraph EVAL["2. 打分评估"]
E["给每个方案打分<br/>cost越低=分配越合理"]
end
subgraph EVOLVE["3. 优胜劣汰 x100代"]
CROSS["交叉<br/>两个好方案"结婚生子"<br/>继承双方优点"]
MUT["变异<br/>随机改变小部分<br/>防止近亲繁殖"]
SELEC["保留最优50个<br/>差的淘汰"]
end
subgraph OUTPUT["4. 输出最优"]
BEST["cost最低的方案<br/>= 最终分配结果"]
end
INIT --> EVAL --> EVOLVE
EVOLVE --> EVAL
EVOLVE --> OUTPUT
style INIT fill:#E3F2FD,stroke:#1976D2
style EVAL fill:#FFF8E1,stroke:#F57C00
style EVOLVE fill:#F3E5F5,stroke:#7B1FA2
style OUTPUT fill:#E8F5E9,stroke:#388E3C
一张图理解"个体"和"基因"
flowchart LR
subgraph 个体["一个候选方案 = 一只蜜蜂"]
T1["任务1"] -->|"分配给"| A0["AGV0"]
T2["任务2"] -->|"分配给"| A2["AGV2"]
T3["任务3"] -->|"分配给"| A0b["AGV0"]
end
subgraph 编码["基因编码 = [AGV0, AGV2, AGV0, ...]"]
CODE["[0, 2, 0, 1, 3, ...]"]
end
style T1 fill:#FFF8E1,stroke:#F57C00
style T2 fill:#FFF8E1,stroke:#F57C00
style T3 fill:#FFF8E1,stroke:#F57C00
style A0 fill:#E8F5E9,stroke:#388E3C
style A2 fill:#E8F5E9,stroke:#388E3C
style CODE fill:#F3E5F5,stroke:#7B1FA2
打分标准：cost越低越好
| 扣分项 | 说明 |
|---|---|
| 距离远 | 每个任务到AGV的曼哈顿距离，越远扣越多 |
| 负载不均 | 一台AGV干太多活，扣(任务数-1)²×5分 |
交叉与变异：进化的两个翅膀
| 操作 | 作用 | 类比 |
|---|---|---|
| 交叉 (80%概率) | 两个体交换基因片段 | 蜜蜂"结婚"，孩子继承父母优点 |
| 变异 (10%概率) | 随机改变某个基因 | 基因突变，防止所有蜜蜂都长得一样 |
效果对比
| 算法 | 找最优 | 负载均衡 | 适合场景 |
|---|---|---|---|
| 贪心（每个任务找最近的） | ❌ 局部最优 | ❌ 可能累死一台 | 实时快速分配 |
| BSO（50×100代搜索） | ✅ 全局近似最优 | ✅ 自动均衡 | 批量离线规划 |
实际效果：20任务/15AGV，cost从40313降到790。
二、交叉与变异操作
交叉：两个体交换基因片段
Individual BSOTaskAllocator::crossover(
const Individual& p1, const Individual& p2) {
Individual child = p1;
// 随机选一个交叉点
std::uniform_int_distribution<int> pointDist(0, p1.genes.size());
int crossPoint = pointDist(rng_);
// 交叉点之后用p2的基因
for (int i = crossPoint; i < static_cast<int>(p1.genes.size()); ++i) {
child.genes[i] = p2.genes[i];
}
return child;
}
变异：随机改变单个基因
Individual BSOTaskAllocator::mutate(
const Individual& ind, int numTasks) {
Individual mutated = ind;
// 每个基因以 mutationRate=0.1 的概率突变
std::uniform_real_distribution<double> probDist(0.0, 1.0);
for (size_t i = 0; i < mutated.genes.size(); ++i) {
if (probDist(rng_) < mutationRate_) {
mutated.genes[i] = taskDist(rng_); // 随机换个AGV
}
}
return mutated;
}
三、BSO与贪心算法对比
| 维度 | 贪心算法 | BSO群体智能 |
|---|---|---|
| 分配方式 | 每个任务选最近的AGV | 50个个体并行搜索100代 |
| 最优性 | 局部最优（给后续留坑） | 近似全局最优 |
| 负载均衡 | ❌ 可能全分配给同一台 | ✅ 适应度含负载惩罚项 |
| 计算开销 | O(n²) | O(popSize×maxIter×n²) |
| 适用场景 | 实时在线分配 | 批量离线分配 |
运行结果示例（20个任务，15台AGV）：
来自 linuxros.cn · linuxROS
BSOTaskAllocator: Allocating 20 tasks to 15 AGVs
iter=0 bestFitness=40313.0 # 初始随机解，cost很高
iter=20 bestFitness=790.0 # 20代后cost大幅下降
iter=40 bestFitness=790.0 # 收敛
iter=80 bestFitness=790.0 # 保持最优
BSOTaskAllocator: Complete, bestCost=790.0 iterations=100
四、实时冲突化解
BSO分配好任务后，AGV在移动过程中仍可能相撞。冲突检测与化解在 step() 每帧执行：
void SimulationCore::checkConflicts() {
currentConflicts_.clear();
for (size_t i = 0; i < agvs_.size(); ++i) {
for (size_t j = i + 1; j < agvs_.size(); ++j) {
auto& agv1 = agvs_[i];
auto& agv2 = agvs_[j];
if (!agv1->isActive() || !agv2->isActive()) continue;
const common::Point& p1 = agv1->position();
const common::Point& p2 = agv2->position();
// 距离<=1（相邻或同格）→ 视为冲突
if (p1 == p2 || p1.manhattanDistance(p2) <= 1) {
Conflict conflict(agv1->id(), agv2->id(), p1, timeStep_);
currentConflicts_.push_back(conflict);
++totalConflicts_;
}
}
}
}
冲突解决策略：较小ID的AGV继续走，较大ID的AGV进入WAITING等待：
void SimulationCore::resolveConflict(const Conflict& conflict) {
auto agv1 = getAGV(conflict.agv1Id);
auto agv2 = getAGV(conflict.agv2Id);
// 较小ID优先通行
if (agv1->id() < agv2->id()) {
agv2->setState(entity::AGVState::WAITING);
waitingAgvIds_.insert(agv2->id());
} else {
agv1->setState(entity::AGVState::WAITING);
waitingAgvIds_.insert(agv1->id());
}
}
五、任务全生命周期流程
flowchart TB
subgraph 生成["1. 任务生成"]
GEN["TaskPool::generate(count)<br/>在空闲格随机生成任务"]
end
subgraph 分配["2. BSO批量分配"]
ALLOC["replanAll()<br/>收集所有空闲AGV位置"]
BSO["BSOTaskAllocator.allocate()<br/>种群50×100代寻优"]
MAPG["任务→AGV映射<br/>assignTask + setTarget"]
end
subgraph 执行["3. 路径规划+移动"]
PLAN["CBS/ECBS多AGV路径规划"]
MOVE["step()逐帧移动"]
CONFLICT{"checkConflicts()<br/>检测到冲突?"}
end
subgraph 完成["4. 任务完成"]
ARRIVE["AGV到达目标"]
COMPLETE["taskPool.completeTask()"]
NEXT["触发BSO重新分配"]
end
GEN --> ALLOC --> BSO --> MAPG
MAPG --> PLAN --> MOVE --> CONFLICT
CONFLICT -->|"冲突"| WAIT["resolveConflict()<br/>一方WAITING"]
WAIT --> PLAN
CONFLICT -->|"无冲突"| MOVE
MOVE -->|"到达"| ARRIVE --> COMPLETE --> NEXT --> ALLOC
style ALLOC fill:#E3F2FD,stroke:#1976D2
style BSO fill:#F3E5F5,stroke:#7B1FA2
style PLAN fill:#E8F5E9,stroke:#388E3C
style CONFLICT fill:#FFF8E1,stroke:#F57C00
style COMPLETE fill:#E8F5E9,stroke:#388E3C
六、常见问题解决
| 问题 | 原因 | 解决 |
|---|---|---|
| BSO不收敛 | 种群太小或迭代不足 | 增大 bsoPopulationSize_ 到100，bsoMaxIterations_ 到200 |
| 冲突频率过高 | 路径规划间隔太长 | 增大 ecbsBound_ 到1.5，牺牲路径质量换规划速度 |
| AGV一直WAITING不恢复 | 对方路径占用了所有通道 | 触发 replanAll() 全局重规划 |
七、总结
BSO的核心是用群体多样性换解的质量：50个个体并行搜索，交叉保持探索、变异跳出局部最优、适应度函数同时考虑距离和负载均衡。冲突化解则是"小ID优先走"的简单优先级策略。
BSO代码只有216行（BSOTaskAllocator.cpp），冲突检测与解决在 SimulationCore.cpp 中各40行，麻雀虽小五脏俱全。
下篇预告：SDL2可视化渲染管线 + ROS2自定义消息/服务/launch文件，看仿真系统如何从"命令行"跃升为"可交互桌面应用+ROS2节点"。
看到这还不点赞？今晚代码必跑飞。看完不转发？Bug跟你到白头。推荐给朋友，一起被坑到永久。评论区见，谁是今天的最强显眼包？👻