专辑论文导读 I 基于多目标松散同步搜索的多目标多智能体异步路径规划

文摘   2024-08-16 09:00   湖北  

  交大学报英文版 论文导读


探|索|科|技|前|沿 强|国|复|兴|有|我

导语


本期推介论文已在《上海交通大学学报(英文版)》第4期“多智能体协同感知与控制”专辑发表。欢迎相关领域的研究者阅读、引用!










多智能体协同感知与控制

专辑

洞见科技新纪元·解锁智能协同奥秘



Multi-Objective Loosely Synchronized Search for Multi-Objective Multi-Agent Path Finding with Asynchronous Actions

基于多目标松散同步搜索的多目标多智能体异步路径规划



上海交通大学自动化系IIC Lab(智能信息控制实验室)

针对多智能体路径规划仍然面临状态空间大、算法运行时间长的问题,且在实际野外环境的应用场景中面临优化目标多及多智能体具有异步行动的难点,提出多目标松散同步(MO-LS)搜索的算法框架。通过结合A*和M*算法,分别提出MO-LS-A*和MO-LS-M*算法。证明了算法的完备性和最优性,并通过设计一系列比较实验来分析影响算法性能的因素,验证了所提出的MO-LS-M*算法相较于经典基于搜索的路径规划在算法性能上具有一定的优势。

欢迎相关领域的研究者转发、引用!


PART.1  本文亮点



1、考虑了在多智能体多目标路径规划过程中的异步行动问题,即在路径规划过程中允许智能体在地图各处以不同速度运动。

2、将M*的亚维度展开技术用于多目标搜索算法过程中,有效减小了基于搜索算法的搜索空间,提高了算法的运行速度。

3、证明了MO-LS-A*/MO-LS-M*算法的完备性和最优性。即算法将找到这个问题所有帕累托最优联合路径,否则算法无解时将在有限时间内终止。


PART.2 实验结果


基于多目标松散同步搜索的多目标多智能体异步路径规划

实验一:
16×16无障碍物的方格地图,两个智能体,两个优化目标。K为智能体的速度范围(对于离散规划时间步长划分的精细度)。测试100次,算法在5 min成功结束即为一次运行成功,记录算法成功率。
实验一是为了验证松散同步搜索在多智能体异步行动时能够有效避免时间维度划分过细,减小搜索空间,进而提升在有限时间内算法运行的成功率。
实验结果表明,使用了松散同步搜索的MO-LS-A*比未使用松散同步搜索的MOA*在不同的时间划分精细度下均能保证较高的成功率,而未使用松散同步搜索的MOA*成功率随着时间划分精细度的提升而降低。实验一验证了松散同步搜索的有效性。

实验二:
在三张不同尺寸地图上测试不同智能体数量、不同优化目标个数下算法运行的成功率(成功率的定义同实验一)。
实验二是为了证明M*的亚维度展开技术能够有效减小多目标搜索算法的搜索空间,减少运行时间,提高成功率。同时测试影响MO-LS-M*算法运行效率的一系列变量。
实验结果表明在相同条件下MO-LS-M*的成功率高于MO-LS-A*,M*的亚维度展开技术能够有效减小多目标搜索算法的搜索空间。而智能体数量、优化目标数、地图尺寸、启发函数膨胀因子都是影响MO-LS-M*算法运行效率的变量。

实验三:
在不同启发函数膨胀因子下MO-LS-M*算法的运行时间,实验结果表明启发函数膨胀因子能够减小算法运行的时间,同时在论文中证明了启发函数膨胀时的有界最优性,因此该实验验证了牺牲算法最优性换取算法运行时间降低的可行性。


研究不足(未来研究补充点)

(1)该研究没有考虑智能体形状

(2)该研究采用离散时间的假设,没有考虑连续时间

(3)该研究主要关注集中式基于搜索的算法,没有考虑分布式的其他方法


PART.3 团队及作者简介



团队介绍:

IIC Lab(智能信息控制实验室)是上海交通大学自动化系下设先进控制与自动化系统研究所的分支研究室之一。

实验室依托控制科学与工程一级学科,以工业和国防应用为背景,结合国际前沿和发展趋势,针对现阶段复杂系统中信息处理所面临的科学问题,对复杂环境下的信息处理、融合以及控制问题等进行广泛和深入的研究。

近五年以来,承担国家级科研项目10余项,国防项目20余项,多名学生在校期间获得国家优秀奖学金、上海市优秀毕业生等荣誉称号,学生在国防科研院所及互联网、金融等知名单位中适应力强,业绩突出,具有极强的发展潜力。


作者简介

杜海阔,上海交通大学电子信息与电气工程学院自动化系硕士研究生。主要研究方向为路径规划以及多智能体强化学习


通讯作者简介

蔡云泽,上海交通大学电子信息与电气工程学院自动化系研究员。主要从事自主态势感知和智能决策在作战指挥系统中的应用,包括:多传感器信息融合,目标检测、定位与跟踪;协同态势评估与预测,智能优化与对抗博弈,任务分配和协同规划等方向研究。



PART.4 引文信息


DU Haikuo (杜海阔), GUO Zhengyu(郭正玉), ZHANG Lulu(章露露), CAI Yunze (蔡云泽). Multi-Objective Loosely Synchronized Search for Multi-Objective Multi-Agent Path Finding with Asynchronous Actions[J]. J Shanghai Jiaotong Univ Sci, 2024, 29(4): 667-677.


文章链接:

https://xuebao.sjtu.edu.cn/sjtu_en/EN/10.1007/s12204-024-2744-x

撰文:杜海阔

编辑:李博文

责任编辑:黄龙旺


感谢关注,欢迎投稿 !

关于我们

《上海交通大学学报》是由教育部主管、上海交通大学主办的自然科学综合性学术刊物。刊登内容主要包括新型电力系统与综合能源、船舶海洋与建筑工程、机械与动力工程、电子信息与电气工程、材料科学与工程等方面的最新研究成果。本刊为中国科技论文统计源核心期刊、CSCD来源期刊、中文核心期刊(北大核心),并被《美国工程索引》(EI)、Scopus、DOAJ等国际权威检索系统所收录。

《上海交通大学学报(英文版)》是由教育部主管、上海交通大学主办的自然科学综合性学术期刊,被 EI、Scopus、DOAJ 等权威检索系统所收录。主要刊登反映基础理论和工程领域实验研究的最新成果,如电子工程和自动化、计算机和通信工程、船舶海洋和建筑工程、材料科学与工程以及生物医学工程等。从 2021 年开始,《上海交通大学学报(英文版)》主要刊登医工交叉研究和人工智能及其在工程中的应用成果。

敬请关注和赐稿!

投稿须知

1.本刊只刊登首发稿,稿件须具有创新性、学术性、科学性和准确性。为保证作者的署名权和知识产权,所有作者应在版权转让协议上签名,须与原稿同时上传。请勿一稿多投、重复内容多次投稿、不同文种重复投稿。

2.本刊为同行评议期刊,审稿结果在4个月内通知作者,在此期间,请勿将稿件投往他处。个别稿件送审时间可能较长。如果作者决定改投他刊或撤稿,请通知编辑部后,再进行处理。

3.在稿件的修改过程中,若超过稿件修改时限30日,编辑部将以作者返回修改稿日期作为投稿日期;无故超过30日,编辑部将对稿件做退稿处理。

4.文责自负,作者同意编辑部根据国家出版规范要求对稿件进行编辑和修改等必要处理。

5.为便于学术信息传播,本刊实行开放获取,收取审稿费和发表费,同时编辑部赠寄当期杂志2册。 

中文版主页https://xuebao.sjtu.edu.cn/CN/1006-2467/home.shtml

英文版主页:https://xuebao.sjtu.edu.cn/sjtu_en/EN/1007-1172/home.shtml

英文版on Springer:https://link.springer.com/journal/12204


   

  

👈学报视频号                    学报b站号👉


扫描二维码   关注我们

Tel:(021)62933373

E-mail:xuebao3373@sjtu.edu.cn


上海交通大学学报
发布学报(自然科学版)最新内容、投稿指南、学报活动,与读者沟通交流
 最新文章