LSRP*让异步多智能体规划变成随时可改进:最多多容纳25%智能体,解成本最多降40%
核心概要
多智能体路径规划长期默认所有智能体同步起步、每条边耗时相同,异步动作下这一假设失效。LSRP*在LSRP的推挤式规则规划之上加入随时搜索,先快速给出可行解,再在运行预算内持续改进。在最多1000个智能体的多张基准地图上,它比LSRP多处理最多25%的智能体,并把LSRP解的成本最多降低40%。
深度剖析
异步动作下的多智能体路径规划现在可以在拿到首个解之后继续变好,而不必在初始解上停住。 此前的LSRP能扩展到大量智能体,但属于无界次优规划器,无法用额外运行时间改进解的质量。 在四张MAPF基准地图、每张20个实例、智能体数最多到1000的测试中,LSRP*比LSRP多处理最多25%的智能体,并把LSRP找到的解成本最多降低40%。
改进来自把到达时间纳入搜索,并用支配规则和重初始化反复重开搜索路径。 LSRP*沿用LSRP的推挤与交换规则补全动作,但把搜索改成深度优先、每次只展开一个后继的惰性展开。 搜索在时间增广状态空间上进行,支配比较同时看成本与每个智能体的到达时间;重初始化按上次改进所用迭代数周期性从根节点重新展开。
在可算出最优解的实例上,改进后的解接近最优。 LSRP*在60秒预算内把初始LSRP解的成本最多精炼约35%,与最优解的差距缩小到几个百分点。 与CBS-AA这一异步动作最优求解器的对比中,LSRP*-SWAP的解成本保持在最优值约几个百分点以内。
启示与展望
演示范围是四张MAPF基准地图上的点智能体,动作时长按智能体与边抽取,单实例时间限制为30秒或60秒;作者提出的下一步包括扩展到占据多个顶点、大小与速度不同的大智能体,以及在真实多机器人平台上验证。
LSRP*本身在杂乱地图上只与基线持平,扩展性优势主要体现在带交换规则的LSRP*-SWAP上;Flip在智能体较少时改进很小,在较大规模时才明显;智能体数增大后60秒内改进有限,首解与终解曲线趋于重合。
