一种边冲突和点冲突解耦的长期多智能体路径规划方法

摘要

本发明涉及智能控制技术领域，具体的说是一种边冲突和点冲突解耦的长期多智能体路径规划方法，包括边冲突避免的滚动时间窗K鲁棒静态路径规划和点冲突避免的实时智能体路径协同，所述K鲁棒边冲突避免的静态路径规划为每当有新任务发布，算法为执行新任务的智能体a

说明书

技术领域

本发明涉及一种边冲突和点冲突解耦的长期多智能体路径规划方法，属于智能控制技术领域。

背景技术

智能仓储是一种使用物联网、信息化和人工智能等技术实现物品运输、存储等一系列操作自动化的新兴仓储模式，与传统仓储对比，智能仓储节约70％的空间及80％的劳动力成本。由于全球化程度、电商需求、物流需求的急遽增长，仓库必须扩大规模、提高运行效率，因此仓储智能化将会成为未来一大热门趋势。在智能仓储场景中，调度系统会不断为智能体分配新的搬运任务，每个任务包含一个装货地点和一个卸货地点，并由智能体将货物从装货地点搬运至卸货地点。由于智能仓储运行中存在大量的智能体同时执行任务协同运动，为了保证智能仓储系统的高效性和可靠性，要求算法为所有智能体规划不发生冲突(主要包括点、边冲突)的路径，同时最小化路径总成本、平均任务完成时间或是最大化系统吞吐量。

经典的多智能体路径规划问题是某时段内的静态问题，问题描述如下：在一个无权无向图G＝(V,E)中(V为表示图中位置的顶点集合，E为表示图中两个相邻位置之间的连接的边集合)，有一组智能体{a

现有方法大都是将长期多智能体优化问题转化为某时段内的静态多智能体路径规划问题，利用传统的多智能体路径规划方法求解，主要方法包括：

(1)使用MAPF求解器在每个时间步为智能体重规划路径，该方法需要耗费大量的时间开销。

(2)使用优先规划的方法，即在每个时间步仅对接收到新任务的智能体进行重规划，该方法无法保证规划路径的最优性与完备性。

(3)使用有限窗口解决冲突的方法，算法以固定的周期对智能体路径进行重规划，每次重规划只解决给定时间窗口内的冲突，该方法避免了一部分由于重规划带来的冗余计算，然而由于智能体无法预知有限窗口外的情况，在一些情况下智能体将会贪心地选择等待来解决短期内的冲突，因此无法保证路径规划的最优性和完备性。

以上方法无法高效地解决长期多智能体路径规划问题，随着问题规模的扩大和任务发布频率的增加，一方面频繁地重规划需要消耗大量的计算资源，无法保障长期多智能体路径规划的实时性；另一方面仅进行局部调整无法保证路径规划的完备性。

有鉴于此特提出本发明来帮助解决上述问题。

发明内容

本发明的目的就在于为了解决上述问题而提供一种边冲突和点冲突解耦的长期多智能体路径规划方法，在智能体规划路径时预测并消解未来可能发生的边冲突，并使用实时智能体路径协同的方法在智能体移动过程中通过近邻智能体信息交换实现点冲突避免。

本发明通过以下技术方案来实现上述目的，一种边冲突和点冲突解耦的长期多智能体路径规划方法，包括边冲突避免的滚动时间窗K鲁棒静态路径规划和点冲突避免的实时智能体路径协同，所述K鲁棒边冲突避免的静态路径规划为每当有新任务发布，算法为执行新任务的智能体a

进一步的，所述K鲁棒边冲突避免的静态路径规划包括以下步骤：

Sa1、底层路径规划器：初始建立一个空的约束集，使用时空A*算法为当前智能体a

Sa2、滚动时间窗的边冲突检测：将当前规划好的路径与还未执行完任务的其他智能体的剩余静态路径进行边冲突检测及预测；

Sa3、添加约束：检测到边冲突

Sa4、重复步骤Sa1至步骤Sa3，直至在步骤Sa2时检测不到可能存在的冲突，将满足当前约束集的路径去掉时间维度作为静态路径，

进一步的，所述步骤Sa2中的预测方法包括以下步骤：

Sa11、对于所有已规划路径的智能体集合A，其静态路径为一系列位置组成的序列，如智能体a

Sa12、当前规划路径P是由一系列时间位置对组成的序列{(v

Sa13、检测当前智能体a

Sa14、令t＝t+1，若t>t

进一步的，所述点冲突避免的实时智能体路径协同包括以下步骤：

Sb1、对于任意智能体a

Sb2、根据不同预约情况判断预约是否成功：

(1)若位置v

(2)若位置v

(3)若位置v

Sb3、预约成功的智能体在下一个时间步将移动到静态路径中的下一个位置，预约失败的智能体在下一个时间步将在原位置等待。

本发明的技术效果和优点：

1、本发明提出边、点冲突分开解决的方法，为每个新任务仅规划一次路径，不需要进行多次重规划，极大程度减小了路径规划的计算量，提高了系统响应单智能体路径规划请求的速度。

2、本发明提出滚动时间窗K鲁棒的边冲突避免静态路径规划，能够保证实际执行过程中智能体在K个时间步中延迟也依旧能够保证规划方案的可行性，保障了长期多智能体路径规划的稳定性。

3、本发明提出实时智能体路径协同的点冲突避免方式，使得智能体在长期运行中根据实际环境调整路径执行方案，更能适应长期多智能体路径规划问题中任务实时发布、未来情况难以预测的特点，同时最小化智能体之间的交换信息量。

附图说明

图1为本发明K鲁棒边冲突避免的静态路径规划流程图。

图2为本发明点冲突避免的实时智能体路径协同流程图。

具体实施方式

下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

本实施例提供了一种边冲突和点冲突解耦的长期多智能体路径规划方法，如图1、2所示，包括边冲突避免的滚动时间窗K鲁棒静态路径规划和点冲突避免的实时智能体路径协同，所述K鲁棒边冲突避免的静态路径规划为每当有新任务发布，算法为执行新任务的智能体a

在滚动时间窗内检测由于智能体发生K步内延迟而引起的边冲突，通过对当前规划路径P添加约束的方法进行冲突解决，静态路径仅由位置序列组成而不含时间维度，智能体将沿为其规划好的静态路径移动，并保证在发生K个意外延迟的情况下仍不与其他智能体发生边冲突，各步骤流程图如图1，所述K鲁棒边冲突避免的静态路径规划包括以下步骤：

Sa1、底层路径规划器：初始建立一个空的约束集，使用时空A*算法为当前智能体a

Sa2、滚动时间窗的边冲突检测：将当前规划好的路径与还未执行完任务的其他智能体的剩余静态路径进行边冲突检测及预测；

由于智能体未来的移动情况会不断地随着新任务发布而改变，算法无法进行精准的冲突检测，考虑到这些问题，本发明采取了一个具有良好效果的预测方法，预测方法包括以下步骤：

Sa11、对于所有已规划路径的智能体集合A，其静态路径为一系列位置组成的序列，如智能体a

Sa12、当前规划路径P是由一系列时间位置对组成的序列{(v

Sa13、检测当前智能体a

Sa14、令t＝y+1，若y>t

Sa3、添加约束：检测到边冲突

Sa4、重复步骤Sa1至步骤Sa3，直至在步骤Sa2时检测不到可能存在的冲突，将满足当前约束集的路径去掉时间维度作为静态路径，

所述点冲突避免的实时智能体路径协同包括以下步骤：

Sb1、对于任意智能体a

Sb2、根据预约情况进行分类，预约分为以下几种情况：

1)若位置v

2)若位置v

3)若位置v

Sb3、预约成功的智能体在下一个时间步将移动到静态路径中的下一个位置，预约失败的智能体在下一个时间步将在原位置等待。

对于本领域技术人员而言，显然本发明不限于上述示范性实施例的细节，而且在不背离本发明的精神或基本特征的情况下，能够以其他的具体形式实现本发明。因此，无论从哪一点来看，均应将实施例看作是示范性的，而且是非限制性的，本发明的范围由所附权利要求而不是上述说明限定，因此旨在将落在权利要求的等同要件的含义和范围内的所有变化囊括在本发明内。不应将权利要求中的任何附图标记视为限制所涉及的权利要求。

此外，应当理解，虽然本说明书按照实施方式加以描述，但并非每个实施方式仅包含一个独立的技术方案，说明书的这种叙述方式仅仅是为清楚起见，本领域技术人员应当将说明书作为一个整体，各实施例中的技术方案也可以经适当组合，形成本领域技术人员可以理解的其他实施方式。