基于停留记忆的多智能体取货配送系统空闲重定位机制研究

《Biomimetics》：Ant-Colony-Inspired Dwell Memory for Traffic-Aware Idle Repositioning in Multi-Agent Pickup and Delivery

　　

摘要

在终身多智能体取货与配送（MAPD）系统中，刚刚完成配送的智能体在等待时必须占据某个位置，而这个位置决定了它下一次取货的距离；目前的解决方法将这一选择留给路径规划器来处理。虽然这种选择优化成本较低——基于需求预测可以应用加权1-中值算法，并在多项式时间内完成——但其短视的决策会导致整体效果不佳：对于某个智能体来说，最佳的位置往往位于需要穿越的车辆路线上，因此各个智能体如果各自独立决策，就会互相干扰；更精确的需求预测反而会加剧这一问题，而不是改善它。蚂蚁群体在面对类似挑战时，通过一种共享的、会随时间变化的信息媒介来解决这一问题，这种媒介由外界事件驱动，而非单个蚂蚁的行为所影响，从而避免了信息被篡改的风险。本文将智能体的空闲重新定位行为视为第三层决策机制，位于任务分配和时空路径查找之下，并为其设计了一种这样的媒介：一个随时间衰减的任务到达强度场，该强度场仅由任务发布情况生成，被称为“停留记忆”。这个机制驱动了一个加权1-中值算法，在该算法中，每个候选位置都会根据所拦截车辆的流量被赋予一个价格，这个价格是根据地图信息预先计算好的。衰减过程可以在线调整；此外，还有一个有限覆盖范围的可达性过滤器，当车队自身占用情况尚未破坏可达性时，该过滤器会重新设定可达性——具体来说，在最多包含16个智能体的车队中，这一机制的准确率可达到次决策的精度。在9种布局和8499次实验中，即使不修改任务分配和路径查找部分，平均服务时间也能缩短32%：这一收益主要体现在回程路段，而非送货路段；需求记忆和结构成本的影响在对车队规模的两个极端情况下表现不同，而非随车队规模增加而累积；效果的范围受到空闲时间的影响，而非地图大小的制约。操作范围的确定是实验结果的一部分，而非疏忽：当空闲时间过短（低于大约10秒），即智能体没有移动时间时，该机制的效果会减弱；在最密集的基准地图上，对于规模最大的车队（拥有74个智能体），效果会减弱。这种效应还受到规划器拥堵的影响，而结构成本并未覆盖这一情况。