一种基于对数模型冲突感知自适应次优因子的路径规划方法

摘要: 本发明涉及多智能体路径规划,更具体的说是涉及一种基于对数模型冲突感知自适应次优因子的路径规划方法。背景技术:1、多智能体路径规划(multi-agentpath...
一种基于对数模型冲突感知自适应次优因子的路径规划方法

本发明涉及多智能体路径规划,更具体的说是涉及一种基于对数模型冲突感知自适应次优因子的路径规划方法。

背景技术:

1、多智能体路径规划(multi-agent path finding,mapf)是指在给定环境地图、多个智能体的起始位置以及目标位置的条件下,为每个智能体规划一条从起始位置到对应目标位置的运动路径,并保证不同智能体在运动过程中不发生相互冲突。

2、在典型离散时间mapf模型中,运行环境通常表示为由节点和边组成的图。智能体在每一个时间步可以从当前位置移动至相邻可通行位置,也可以停留在当前位置等待。

3、当两个智能体在同一时间步占据同一位置时,产生顶点冲突;当两个智能体在同一时间段沿同一连接边向相反方向移动时,产生边冲突。

4、现有基于冲突搜索的mapf算法通常采用高层搜索和低层搜索相结合的两级搜索结构。

5、高层搜索负责维护当前多智能体路径集合,检测路径集合中存在的智能体冲突,并针对冲突生成相应约束;低层搜索则针对受到新增约束影响的智能体重新执行单智能体路径搜索,以获得满足约束条件的替代路径。

6、通过高层冲突处理与低层路径重新规划的重复执行,最终得到不存在智能体间冲突的路径集合。

7、eecbs(explicit estimation conflict-based search)是在上述两级搜索结构基础上采用有界次优机制的一种多智能体路径规划方法。

8、eecbs需要预先设置一个全局次优因子,且满足:

9、(1)

10、该参数用于限定eecbs搜索过程中允许的次优范围。

11、传统eecbs针对不同智能体执行低层focal搜索时,统一采用固定全局次优因子w。

12、设针对智能体执行低层搜索时,open集合中的最小估计总代价为,候选节点n对应的估计总代价为,则传统eecbs低层focal候选条件可以表示为:

13、(2)

14、满足式(2)的节点可以进入对应focal候选集合,并根据eecbs低层搜索的次级评价方式进一步选择待扩展节点。

15、因此,在传统eecbs中,不同智能体虽然所处位置、路径结构以及参与冲突的数量可能存在明显差异,但在低层搜索过程中均受到相同固定次优因子w的控制。

16、然而,在实际mapf环境中,不同智能体参与冲突的程度通常不同。部分智能体可能位于狭窄通道、障碍物边缘或者路径交汇区域,频繁与其他智能体发生冲突;而部分智能体可能位于相对开放的区域,仅参与少量冲突甚至不参与冲突。

17、因此,不同智能体对于低层路径搜索灵活度的实际需求并不相同,而传统固定次优因子无法体现上述差异。

18、现有统一搜索边界分配方式至少存在以下问题。

19、1. 固定次优因子无法反映不同智能体之间的冲突差异

20、传统eecbs针对所有智能体统一采用全局固定次优因子w。

21、但是,在同一个mapf实例中,不同智能体参与冲突的次数可能存在明显差异。

22、对于参与冲突较少的智能体,其当前路径与其他智能体之间的相互影响较小,对较大路径调整空间的需求通常较低。

23、对于参与冲突较多的智能体,其当前路径可能位于局部拥堵区域,或者与多个其他智能体产生路径竞争,因此需要相对较大的路径调整空间,以寻找满足新增约束的替代路径。

24、由此可见,统一固定次优因子难以同时适应不同冲突程度智能体的搜索需求。

25、2. 较大的固定次优因子可能增加低冲突智能体的不必要搜索

26、根据式(2),当全局次优因子w增大时,满足focal候选条件的节点范围也会扩大。

27、对于高冲突智能体而言,较大的候选范围能够提供更多路径调整选择;但是对于低冲突智能体而言,其实际可能并不需要如此大的搜索范围。

28、如果所有智能体均统一采用较大的w,低冲突智能体也可能搜索更多绕行节点、等待节点以及替代路径节点,从而增加节点生成、维护和扩展计算。

29、3. 较小的固定次优因子可能限制高冲突智能体的路径调整空间

30、如果为了减少低层搜索开销而统一减小w,则能够进入focal集合的候选节点范围相应减小。

31、对于高冲突智能体而言,较小的候选范围可能限制其寻找替代路径的能力。

32、受到高层新增约束后,重新规划得到的路径虽然能够满足当前约束,但仍可能继续与其他智能体产生冲突,从而使高层生成更多ct节点,并进一步触发低层重新规划。

33、因此,传统固定次优因子存在以下矛盾:

34、较大的固定次优因子可能增加低冲突智能体的不必要搜索,而较小的固定次优因子又可能限制高冲突智能体的路径调整灵活性。

35、4. eecbs高层已有冲突信息没有被充分用于低层参数配置

36、eecbs高层搜索在进行冲突检测过程中已经能够获得当前路径集合中的冲突以及参与冲突的智能体。

37、因此,可以进一步统计每个智能体参与冲突的次数,并利用该信息描述不同智能体当前的冲突程度。

38、然而,传统eecbs主要利用冲突信息执行冲突选择和约束生成,而针对低层搜索仍统一采用固定次优因子w,没有进一步根据智能体自身参与冲突的数量配置个体化次优因子。

39、5. 固定次优因子无法适应搜索过程中冲突状态的变化

40、随着高层不断产生新的约束,被约束智能体的路径会发生变化,各智能体之间的冲突关系也可能随之变化。

41、某一智能体在初始路径集合中可能仅参与少量冲突,但在后续路径重新规划之后可能进入新的路径交汇区域;原本冲突较多的智能体也可能在重新规划后避开原冲突区域。

42、因此,在搜索全过程中始终采用固定次优因子,不能根据当前ct节点中的冲突状态变化调整不同智能体的搜索灵活度。

43、因此,提出一种基于对数模型冲突感知自适应次优因子的路径规划方法,来解决现有技术存在的困难,是本领域技术人员亟需解决的问题。

技术实现思路

1、有鉴于此,本发明提供了一种基于对数模型冲突感知自适应次优因子的路径规划方法,用于解决现有技术中存在的技术问题。

2、为了实现上述目的,本发明提供如下技术方案:

3、一种基于对数模型冲突感知自适应次优因子的路径规划方法,包括以下步骤:

4、s1、输入多智能体路径规划mapf任务参数,mapf任务参数包含环境地图、智能体集合、各智能体的起始位置、目标位置、全局次优上限值以及个体次优因子分配策略;

5、s2、生成各智能体初始路径,根据全部智能体初始路径构建根冲突树ct节点;

6、s3、对当前ct节点对应的路径集合开展冲突检测;若未检测到冲突,直接输出当前路径集合作为规划结果;若检测存在冲突,则统计当前ct节点下每个智能体的冲突参与次数;

7、s4、根据各智能体的冲突参与次数,通过对数映射模型,分别计算每个智能体对应的个体次优因子;

8、s5、选择待解决冲突,针对参与冲突的智能体生成约束条件,分裂得到子ct节点;

9、s6、对受新增约束影响的智能体,采用对应智能体的个体次优因子替换全局次优上限值,执行低层focal搜索完成重新路径规划;

10、s7、使用重新规划得到的路径更新子ct节点,将更新后的有效子ct节点加入高层搜索队列;循环执行步骤s3-s7,直至输出无冲突的路径集合。

11、可选的,冲突包括顶点冲突和边冲突;

12、顶点冲突是两个智能体在同一时间步占据同一位置;

13、边冲突是两个智能体在同一时间段沿同一条边相向反向移动;

14、统计冲突参与次数时,顶点冲突与边冲突均计入对应智能体的冲突参与次数。

15、可选的,s4中,先计算当前ct节点下全部智能体冲突参与次数的最大冲突次数;当最大冲突次数为0时,直接输出当前路径集合;当最大冲突次数大于0时,执行个体次优因子计算。

16、可选的,通过对数映射模型,分别计算每个智能体对应的个体次优因子的具体公式如下:

17、

18、其中,表示智能体在ct节点n下的个体次优因子;w表示传统eecbs预先设置的全局次优因子,同时作为所有个体次优因子的最大允许值;表示智能体在当前节点对应路径集合中参与冲突的次数;表示当前ct节点中所有智能体冲突次数的最大值;ln(x)表示自然对数函数。

19、可选的,当智能体无冲突参与、时,计算得到个体次优因子;当智能体冲突参与次数等于最大冲突次数时,计算得到个体次优因子。

20、可选的,个体次优因子分配策略包括静态分配策略sw-eecbs以及动态分配策略dw-eecbs;

21、静态分配策略sw-eecbs仅在根ct节点执行一次个体次优因子计算,后续ct节点直接复用计算结果;

22、动态分配策略dw-eecbs针对每一个待扩展的ct节点,均重新统计冲突参与次数并重新计算每个智能体的个体次优因子。

23、可选的,s6中低层focal搜索的候选判定条件为:

24、

25、构建focal候选集合:

26、其中,n表示低层候选节点,表示智能体对应候选节点的估计总代价,表示当前open集合中的最小估计总代价,表示智能体在ct节点n下的个体次优因子。

27、经由上述的技术方案可知,与现有技术相比,本发明公开提供了一种基于对数模型冲突感知自适应次优因子的路径规划方法,其有益效果为:

28、1)、实现次优因子的个体化配置:

29、根据不同智能体实际参与冲突的次数计算对应的个体次优因子,使低层搜索参数能够体现不同智能体之间真实存在的冲突差异;

30、2)、减少低冲突智能体不必要的候选搜索:

31、对于冲突次数较少的智能体,其个体次优因子较小,使focal候选范围相应减小,从而降低不必要候选节点进入低层搜索范围的可能性;

32、3)、提高高冲突智能体的路径调整灵活性:

33、对于冲突次数较多的智能体,其个体次优因子相对较大,可以在更大的次优允许范围内选择候选节点,从而增加寻找满足约束替代路径的灵活性;

34、4)、充分利用eecbs高层已有冲突信息:

35、本发明直接利用eecbs冲突检测过程中已经获得的智能体冲突信息,无需额外建立复杂的外部评价模型,从而建立高层冲突状态与低层搜索参数之间的反馈关系;

36、5)、对数模型兼顾冲突敏感性与参数稳定性:

37、对数函数使个体次优因子随着冲突次数单调增加,同时能够对较大的冲突数量进行非线性压缩,使参数变化更加平稳;

38、6)、不突破原eecbs全局次优因子上限:

39、本发明保证:

40、

41、因此,个体次优因子的自适应调整始终受到原全局次优上限约束;

42、7)、对原eecbs结构改动较小:

43、本发明保留eecbs高层ct搜索、ees节点选择、冲突检测、约束生成以及低层focal搜索基本结构,主要增加冲突计数、对数函数计算及个体次优因子调用过程,便于在现有eecbs实现基础上进行集成;

44、8)、提高多智能体路径规划整体求解效率:

45、通过减少低冲突智能体不必要的搜索范围,同时为高冲突智能体配置相适应的搜索灵活度,可以更加合理地利用低层搜索资源,从而降低整体搜索开销并提高多智能体路径规划效率。