一种基于冲突搜索的有界次优智能体路径规划方法及系统
本发明涉及路径规划，尤其是涉及一种基于冲突搜索的有界次优智能体路径规划方法及系统。
背景技术：
1、多智能体路径规划问题的任务是为多个智能体（如机器人或agv小车）规划出无冲突的路径，使它们能够在共享环境中同时行动而不产生冲突，其关键的挑战在于，随着智能体数量的增加，路径规划的复杂度急剧上升，在求解时间和解的质量之间取得合理的权衡是面临的关键问题。
2、基于冲突的搜索算法(conflict-based-search,cbs)是解决多智能体路径规划问题的一个经典方法。它采用了一种两级策略，分为高级搜索和低级搜索，cbs算法的高级搜索负责检测多个智能体路径中的冲突，并通过添加约束生成新的节点；低级搜索则为每个智能体在满足这些约束的情况下重新规划路径，通常使用a*算法。高级搜索负责全局优化，低级搜索负责单个智能体的路径求解，两者协同作用以找到无冲突的多智能体路径方案。cbs保证了解的最优性和完备性，即能够找到可行解，并且当解存在时，算法一定能找到。
3、该算法为保证解的最优性，面临若干主要问题：首先，mapf问题是np难的，cbs作为可行解法，处理智能体数量有限，返回可行解的求解时间往往过长。其次，高级搜索扩展成本最小的节点来验证最优性，导致相同约束在不同节点重复添加，产生大量冗余和回溯，延长了求解时间。再次，cbs在处理某些冲突时效率低。当前成本无解时，cbs需验证所有路径不可行后才能继续扩展节点。对于成本增加较大的冲突，cbs需验证所有低于该成本的方案是否不可行，耗费大量计算资源。
技术实现思路
1、为了解决上述提到的问题，本发明在保留cbs完整性的基础上，提出一种基于冲突搜索的有界次优算法，旨在通过放宽目标节点成本限制和引入基于基数冲突及内部约束的新排序策略，提高cbs算法的求解效率。
2、第一方面，本发明提供的一种基于冲突搜索的有界次优智能体路径规划方法，采用如下的技术方案：
3、一种基于冲突搜索的有界次优智能体路径规划方法，包括：
4、获取多智能体道路信息；
5、初始化根节点，根据多智能体道路信息生成最短路径；
6、检测路径是否存在冲突，若无冲突，直接输出最短路径作为最终解；
7、若存在冲突，通过节点插入进行冲突解决并生成新子节点；
8、对生成的新子节点进行路径更新；
9、检查新子节点并重复进行冲突检测，更新直至找到可行解。
10、进一步地，所述初始化根节点，包括将根节点的约束集root.constraints置为空集，用于表示当前节点无约束条件，保证后续搜索在无约束的条件下进行。
11、进一步地，所述根据多智能体道路信息生成最短路径，包括通过低级搜索为每个智能体生成初始路径，包括调用低级搜索a^*算法，依次为k个智能体计算从起点到终点的最短路径，并将搜索结果存储于root.solution中。
12、进一步地，所述检测路径是否存在冲突，包括判断两个智能体 和是否在相同的时间步占用相同的顶点或相同的边，如果冲突发生在顶点，则冲突被表示为，如果冲突发生在边上，则冲突被表示为。
13、进一步地，所述通过节点插入进行冲突解决并生成新的子节点，包括当存在冲突时，将root节点插入open列表中，检查节点是否满足次优界限并插入focal列表，同时选择focal列表中的最佳节点进行扩展,针对冲突智能体生成新子节点。
14、进一步地，所述对生成的子节点进行路径更新，包括将冲突智能体a_i的约束添加到新节点的约束集a.constraints中，并更新其解决方案a.solution，通过再次调用低级搜索为冲突智能体生成新的路径。
15、进一步地，所述检查新子节点并重复进行冲突检测，更新直至找到可行解，包括检查新生成子节点的成本值，若成本小于无穷大，则将新子节点插入open列表中，重复进行冲突检测和路径更新，直到找到无冲突的解。
16、第二方面，一种基于冲突搜索的有界次优智能体路径规划系统，包括：
17、数据获取模块，被配置为，获取多智能体道路信息；
18、路径生成模块，被配置为，初始化根节点，根据多智能体道路信息生成最短路径；
19、冲突检测模块，被配置为，检测路径是否存在冲突，若无冲突，直接输出最短路径作为最终解；
20、冲突解决模块，被配置为，若存在冲突，通过节点插入进行冲突解决并生成新子节点；
21、路径更新模块，被配置为，对生成的新子节点进行路径更新；
22、更新迭代模块，被配置为，检查新子节点并重复进行冲突检测，更新直至找到可行解。
23、第三方面，本发明提供一种计算机可读存储介质，其中存储有多条指令，所述指令适于由终端设备的处理器加载并执行所述的一种基于冲突搜索的有界次优智能体路径规划方法。
24、第四方面，本发明提供一种终端设备，包括处理器和计算机可读存储介质，处理器用于实现各指令；计算机可读存储介质用于存储多条指令，所述指令适于由处理器加载并执行所述的一种基于冲突搜索的有界次优智能体路径规划方法。
25、综上所述，本发明具有如下的有益技术效果：
26、本发明提出一种基于冲突搜索的有界次优智能体路径规划方法，通过引入focal列表及改进的节点优先级排序策略，对冲突解决过程进行了优化。该方法允许在次优解范围内选择无冲突但成本较高的节点作为目标节点，并优先扩展基数冲突少、内部约束数量多的节点，避免了冗余回溯操作和低效验证。高层搜索通过focal列表选择节点进行扩展，低层搜索则通过路径重规划更新满足约束的最优路径。该方法既保证了完备性，又在可接受的次优界限内实现了解的快速收敛，显著减少了高级搜索的节点扩展数量和低层路径重规划次数，有效降低了整体计算量，能够高效地为多智能体路径规划问题求出合理解。
技术特征：
1.一种基于冲突搜索的有界次优智能体路径规划方法，其特征在于，包括：
2.根据权利要求1所述的一种基于冲突搜索的有界次优智能体路径规划方法，其特征在于，所述初始化根节点，包括将根节点的约束集root.constraints置为空集，用于表示当前节点无约束条件，保证后续搜索在无约束的条件下进行。
3.根据权利要求2所述的一种基于冲突搜索的有界次优智能体路径规划方法，其特征在于，所述根据多智能体道路信息生成最短路径，包括通过低级搜索为每个智能体生成初始路径，包括调用低级搜索a^*算法，依次为k个智能体计算从起点到终点的最短路径，并将搜索结果存储于root.solution中。
4.根据权利要求3所述的一种基于冲突搜索的有界次优智能体路径规划方法，其特征在于，所述检测路径是否存在冲突，包括判断两个智能体 和是否在相同的时间步占用相同的顶点或相同的边，如果冲突发生在顶点，则冲突被表示为，如果冲突发生在边上，则冲突被表示为。
5.根据权利要求4所述的一种基于冲突搜索的有界次优智能体路径规划方法，其特征在于，所述通过节点插入进行冲突解决并生成新的子节点，包括当存在冲突时，将root节点插入open列表中，检查节点是否满足次优界限并插入focal列表，同时选择focal列表中的最佳节点进行扩展,针对冲突智能体生成新子节点。
6.根据权利要求5所述的一种基于冲突搜索的有界次优智能体路径规划方法，其特征在于，所述对生成的子节点进行路径更新，包括将冲突智能体a_i的约束添加到新节点的约束集a.constraints中，并更新其解决方案a.solution，通过再次调用低级搜索为冲突智能体生成新的路径。
7.根据权利要求6所述的一种基于冲突搜索的有界次优智能体路径规划方法，其特征在于，所述检查新子节点并重复进行冲突检测，更新直至找到可行解，包括检查新生成子节点的成本值，若成本小于无穷大，则将新子节点插入open列表中，重复进行冲突检测和路径更新，直到找到无冲突的解。
8.一种基于冲突搜索的有界次优智能体路径规划系统，其特征在于，包括：
技术总结
本发明涉及路径规划技术领域，尤其是涉及一种基于冲突搜索的有界次优智能体路径规划方法及系统。方法包括获取多智能体道路信息；初始化根节点，根据多智能体道路信息生成最短路径；检测路径是否存在冲突，若无冲突，直接输出最短路径作为最终解；若存在冲突，通过节点插入进行冲突解决并生成新子节点；对生成的新子节点进行路径更新；检查新子节点并重复进行冲突检测，更新直至找到可行解。本发明提出一种基于冲突搜索的有界次优智能体路径规划方法，通过引入FOCAL列表及改进的节点优先级排序策略，对冲突解决过程进行了优化。
技术研发人员：童向荣,王子晗,王莹洁,童兰昕,张兴林,王良,程翔,张强
受保护的技术使用者：烟台大学
技术研发日：
技术公布日：2024/12/5