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

In recent years,the path planning for multi-agent technology has gradually matured,and has made breakthrough progress.The main difficulties in path planning for multi-agent are large state space,long algorithm running time,multiple optimization objectives,and asynchronous action of multiple agents.To solve the above problems,this paper first introduces the main problem of the research:multi-objective multi-agent path finding with asynchronous action,and proposes the algorithm framework of multi-objective loose synchronous(MO-LS)search.By combining A*and M*,MO-LS-A*and MO-LS-M*algorithms are respectively proposed.The completeness and optimality of the algorithm are proved,and a series of comparative experiments are designed to analyze the factors affecting the performance of the algorithm,verifying that the proposed MO-LS-M*algorithm has certain advantages.

An Improved Bounded Conflict-Based Search for Multi-AGV Pathfinding in Automated Container Terminals

As the number of automated guided vehicles(AGVs)within automated container terminals(ACT)continues to rise,conflicts have becomemore frequent.Addressing point and edge conflicts ofAGVs,amulti-AGVconflict-free path planning model has been formulated to minimize the total path length of AGVs between shore bridges and yards.For larger terminalmaps and complex environments,the grid method is employed to model AGVs’road networks.An improved bounded conflict-based search(IBCBS)algorithmtailored to ACT is proposed,leveraging the binary tree principle to resolve conflicts and employing focal search to expand the search range.Comparative experiments involving 60 AGVs indicate a reduction in computing time by 37.397%to 64.06%while maintaining the over cost within 1.019%.Numerical experiments validate the proposed algorithm’s efficacy in enhancing efficiency and ensuring solution quality.

Development of Multi-Agent-Based Indoor 3D Reconstruction

Large-scale indoor 3D reconstruction with multiple robots faces challenges in core enabling technologies.This work contributes to a framework addressing localization,coordination,and vision processing for multi-agent reconstruction.A system architecture fusing visible light positioning,multi-agent path finding via reinforcement learning,and 360°camera techniques for 3D reconstruction is proposed.Our visible light positioning algorithm leverages existing lighting for centimeter-level localization without additional infrastructure.Meanwhile,a decentralized reinforcement learning approach is developed to solve the multi-agent path finding problem,with communications among agents optimized.Our 3D reconstruction pipeline utilizes equirectangular projection from 360°cameras to facilitate depth-independent reconstruction from posed monocular images using neural networks.Experimental validation demonstrates centimeter-level indoor navigation and 3D scene reconstruction capabilities of our framework.The challenges and limitations stemming from the above enabling technologies are discussed at the end of each corresponding section.In summary,this research advances fundamental techniques for multi-robot indoor 3D modeling,contributing to automated,data-driven applications through coordinated robot navigation,perception,and modeling.

Optimal path finding algorithms based on SLSD road network model

A solution to compute the optimal path based on a single-line-single-directional（SLSD）road network model is proposed.Unlike the traditional road network model,in the SLSD conceptual model,being single-directional and single-line style,a road is no longer a linkage of road nodes but abstracted as a network node.Similarly,a road node is abstracted as the linkage of two ordered single-directional roads.This model can describe turn restrictions,circular roads,and other real scenarios usually described using a super-graph.Then a computing framework for optimal path finding（OPF）is presented.It is proved that classical Dijkstra and A algorithms can be directly used for OPF computing of any real-world road networks by transferring a super-graph to an SLSD network.Finally,using Singapore road network data,the proposed conceptual model and its corresponding optimal path finding algorithms are validated using a two-step optimal path finding algorithm with a pre-computing strategy based on the SLSD road network.

Dynamic A^*path finding algorithm and 3D lidar based obstacle avoidance strategy for autonomous vehicles

This paper presents a novel dynamic A^*path finding algorithm and 3D lidar based local obstacle avoidance strategy for an autonomous vehicle.3D point cloud data is collected and analyzed in real time.Local obstacles are detected online and a 2D local obstacle grid map is constructed at 10 Hz/s.The A^*path finding algorithm is employed to generate a local path in this local obstacle grid map by considering both the target position and obstacles.The vehicle avoids obstacles under the guidance of the generated local path.Experiment results have shown the effectiveness of the obstacle avoidance navigation algorithm proposed.

Distributed collaborative complete coverage path planning based on hybrid strategy

Collaborative coverage path planning(CCPP) refers to obtaining the shortest paths passing over all places except obstacles in a certain area or space. A multi-unmanned aerial vehicle(UAV) collaborative CCPP algorithm is proposed for the urban rescue search or military search in outdoor environment.Due to flexible control of small UAVs, it can be considered that all UAVs fly at the same altitude, that is, they perform search tasks on a two-dimensional plane. Based on the agents’ motion characteristics and environmental information, a mathematical model of CCPP problem is established. The minimum time for UAVs to complete the CCPP is the objective function, and complete coverage constraint, no-fly constraint, collision avoidance constraint, and communication constraint are considered. Four motion strategies and two communication strategies are designed. Then a distributed CCPP algorithm is designed based on hybrid strategies. Simulation results compared with patternbased genetic algorithm(PBGA) and random search method show that the proposed method has stronger real-time performance and better scalability and can complete the complete CCPP task more efficiently and stably.

System Vulnerability Analysis Using Graph Pathfinding Strategies in Partitioned Networks

In this paper, a new method has been introduced to find the most vulnerable lines in the system dynamically in an interconnected power system to help with the security and load flow analysis in these networks. Using the localization of power networks, the power grid can be divided into several divisions of sub-networks in which, the connection of the elements is stronger than the elements outside of that division. By using our proposed method, the probable important lines in the network can be identified to do the placement of the protection apparatus and planning for the extra extensions in the system. In this paper, we have studied the pathfinding strategies in most vulnerable line detection in a partitioned network. The method has been tested on IEEE39-bus system which is partitioned using hierarchical spectral clustering to show the feasibility of the proposed method.

A greedy path planning algorithm based on pre-path-planning and real-time-conflict for multiple automated guided vehicles in large-scale outdoor scenarios

With the wide application of automated guided vehicles(AGVs) in large scale outdoor scenarios with complex terrain,the collaborative work of a large number of AGVs becomes the main trend.The effective multi-agent path finding(MAPF) algorithm is urgently needed to ensure the efficiency and realizability of the whole system. The complex terrain of outdoor scenarios is fully considered by using different values of passage cost to quantify different terrain types. The objective of the MAPF problem is to minimize the cost of passage while the Manhattan distance of paths and the time of passage are also evaluated for a comprehensive comparison. The pre-path-planning and real-time-conflict based greedy(PRG) algorithm is proposed as the solution. Simulation is conducted and the proposed PRG algorithm is compared with waiting-stop A^(*) and conflict based search(CBS) algorithms. Results show that the PRG algorithm outperforms the waiting-stop A^(*) algorithm in all three performance indicators,and it is more applicable than the CBS algorithm when a large number of AGVs are working collaboratively with frequent collisions.

Multi-Agent Path Planning Method Based on Improved Deep Q-Network in Dynamic Environments

The multi-agent path planning problem presents significant challenges in dynamic environments,primarily due to the ever-changing positions of obstacles and the complex interactions between agents’actions.These factors contribute to a tendency for the solution to converge slowly,and in some cases,diverge altogether.In addressing this issue,this paper introduces a novel approach utilizing a double dueling deep Q-network(D3QN),tailored for dynamic multi-agent environments.A novel reward function based on multi-agent positional constraints is designed,and a training strategy based on incremental learning is performed to achieve collaborative path planning of multiple agents.Moreover,the greedy and Boltzmann probability selection policy is introduced for action selection and avoiding convergence to local extremum.To match radar and image sensors,a convolutional neural network-long short-term memory(CNN-LSTM)architecture is constructed to extract the feature of multi-source measurement as the input of the D3QN.The algorithm’s efficacy and reliability are validated in a simulated environment,utilizing robot operating system and Gazebo.The simulation results show that the proposed algorithm provides a real-time solution for path planning tasks in dynamic scenarios.In terms of the average success rate and accuracy,the proposed method is superior to other deep learning algorithms,and the convergence speed is also improved.

多机器人在网格环境约束下的运动策略

针对多智能体在网格环境下的寻路与避障规划问题,提出一种分布式、基于深度强化学习的多机器人避障导航方法。该方法基于最近策略优化算法(PPO)用于离散决策下的改进方法进行训练得到的策略模型,该模型通过每个智能体自身的前序多帧仿真激光雷达距离信息,生成符合预设规范的动作,实现多机器人系统在不同环境中的寻路避障。该模型在训练过程中通过引入密度奖励、距离奖励以及步长惩罚,提高了智能体在场景当中的避障寻路能力,减轻了拥塞、死锁等问题的发生,减少了无效路径生成。实验部分在仿真环境中对模型在随机场景、复杂交互场景、障碍场景多个场景进行实验,证明了该模型相比于集中式规划方法大大降低了规划时间,提高了泛化性和稳定性。通过与其他分布式方法相比,证明了所提到的密度、距离奖励设置对智能体安全快速完成任务具有良好作用,在规划效果上减小了与集中式规划方式的差距。

面向多无人车的目标点分配和协同路径规划算法

针对多智能体路径搜索算法在非指定式多车协同路径规划问题中路径冗长,计算效率低等缺陷,提出协同目标点分配路径规划算法Nutcracker-CBS。首先构建紧耦合目标点分配MAPF框架,实现目标点分配和路径构建的联合寻优;针对目标点分配模块,提出改进的星鸦优化算法,增量式求解分配问题,缩短模块用时;针对路径构建模块,提出改进的MAPF算法,通过回退式约束构建机制,引入避碰路径估计的绕道机制和数据共享底层路径规划机制,提升效率和路径质量。数据集实验中,Nutcracker-CBS时耗相比SOTA算法减少90.37%;目标点分配模块求解耗时减少86.76%;MAPF模块6 s内构建100辆无人车路径,平均路径长度缩短6.058%。实际实验中路径总和与系统运行时长分别减少55.26%和61.29%,提升了多机器人系统的效率,降低了路径长度。

基于OSG引擎的森林火势蔓延仿真系统关键技术研究

针对森林火势蔓延趋势的仿真推演需求,以及森林消防队伍的行动路线选择和实时路径生成的需要,提出了一种融合数字高程信息(digital elevation model,DEM)的扩展晶格模型,将地形的植被、受灾属性与地理高程信息进行结合,通过实时运算得到结果数据并转换为可渲染的资源形式,利用OSG三维渲染引擎将其呈现到最终用户层面。借助这一数据结构以及对应的关键算法技术的研究实现,完成了一套较为完整的森林火势蔓延趋势仿真和灭火演练系统。该系统具有灵活性高,仿真效率和效果较好,支持各种并行计算方法的特点,可以在相关行业和系统中广泛推广和使用。

基于强化和模仿学习的多智能体寻路干扰者鉴别通信机制

现有的基于通信学习的多智能体路径规划(multi-agent path finding,MAPF)方法大多可扩展性较差或者聚合了过多冗余信息,导致通信低效。为解决以上问题,提出干扰者鉴别通信机制(DIC),通过判断视场(field of view,FOV)中央智能体的决策是否因邻居的存在而改变来学习排除非干扰者的简洁通信,成功过滤了冗余信息。同时进一步实例化DIC,开发了一种新的高度可扩展的分布式MAPF求解器,基于强化和模仿学习的干扰者鉴别通信算法(disruptor identifiable communication based on reinforcement and imitation learning algorithm,DICRIA)。首先,由干扰者鉴别器配合DICRIA的策略输出层识别出干扰者;其次,在两轮通信中分别完成对干扰者与通信意愿发送方的信息更新;最后,DICRIA根据各模块的编码结果输出最终决策。实验结果表明,DICRIA的性能几乎在所有环境设置下都优于其他同类求解器,且相比基线求解器,成功率平均提高了5.2%。尤其在大尺寸地图的密集型问题实例下,DICRIA的成功率相比基线求解器甚至提高了44.5%。

带障碍物惩罚因子的多机器人路径规划

轻载环境中,复杂障碍物区域将引起机器人之间局部冲突加剧,进而导致路径求解效率下降,针对该问题,提出轻载环境下带障碍物惩罚因子的多机器人路径规划方法。在基于冲突搜索(conflict-based search,CBS)算法框架的下层单机规划过程中,通过对即将拓展机器人位置的周围障碍物分布类型进行判断,赋予与之对应的障碍物惩罚因子;对路径规划过程中的惩罚因子进行累加,作为单机规划的启发值对路径进行选取;结合CBS算法框架的上层冲突消解策略进行多机器人的路径规划与冲突协调。测试结果表明,在10%障碍物分布的轻载环境中,所提算法的求解时间约为CBS算法的81.38%~83.67%,二叉约束树(constraint tree,CT)拓展量为CBS算法的60.14%~71.66%。在Gazebo中仿真表明,所提方法可减小通过复杂障碍物区域的次数。

Efficient Route Planning for Real-Time Demand-Responsive Transit

Demand Responsive Transit (DRT) responds to the dynamic users’ requests without any fixed routes and timetablesand determines the stop and the start according to the demands. This study explores the optimization of dynamicvehicle scheduling and real-time route planning in urban public transportation systems, with a focus on busservices. It addresses the limitations of current shared mobility routing algorithms, which are primarily designedfor simpler, single origin/destination scenarios, and do not meet the complex demands of bus transit systems. Theresearch introduces an route planning algorithm designed to dynamically accommodate passenger travel needsand enable real-time route modifications. Unlike traditional methods, this algorithm leverages a queue-based,multi-objective heuristic A∗ approach, offering a solution to the inflexibility and limited coverage of suburbanbus routes. Also, this study conducts a comparative analysis of the proposed algorithm with solutions based onGenetic Algorithm (GA) and Ant Colony Optimization Algorithm (ACO), focusing on calculation time, routelength, passenger waiting time, boarding time, and detour rate. The findings demonstrate that the proposedalgorithmsignificantly enhances route planning speed, achieving an 80–100-fold increase in efficiency over existingmodels, thereby supporting the real-time demands of Demand-Responsive Transportation (DRT) systems. Thestudy concludes that this algorithm not only optimizes route planning in bus transit but also presents a scalablesolution for improving urban mobility.

多智能体路径规划技术研究综述

针对多智能体路径规划(multi-agent path finding, MAPF)问题研究的算法在户外危险场地、智能仓储系统和城市道路网络等领域有着广泛的应用。根据不同的求解思路,关于MAPF问题研究设计的算法主要可以分为基于搜索的传统算法和基于学习的智能算法2类。在基于搜索的传统算法研究中,按照路径规划效果不同,又可分为最优MAPF算法和次优MAPF算法。最优MAPF算法主要分为基于A~*的搜索、基于代价增长树的搜索(increasing cost tree search, ICTS)和基于冲突的搜索(conflict-based search, CBS)这3类;次优MAPF算法主要分为无边界次优的算法和有边界次优的算法2类。基于学习的智能MAPF算法可以大致分为结合专家经验的算法和基于图神经网络(graph neural network, GNN)的算法2类。根据上述分类介绍了近年来具有代表性的研究成果,分析了各种算法的特点,并对MAPF问题未来的研究方向进行了展望。

基于请求与应答通信机制和局部注意力机制的多机器人强化学习路径规划方法

为降低多机器人在动态环境下路径规划的阻塞率,基于深度强化学习方法框架Actor-Critic,设计一种基于请求与应答通信机制和局部注意力机制的分布式深度强化学习路径规划方法(DCAMAPF)。在Actor网络,基于请求与应答通信机制,每个机器人请求视野内的其他机器人的局部观测信息和动作信息,进而规划出协同的动作策略。在Critic网络,每个机器人基于局部注意力机制将注意力权重动态地分配到在视野内成功应答的其他机器人局部观测和动作信息上。实验结果表明,与传统动态路径规划方法D*Lite、最新的分布式强化学习方法MAPPER和最新的集中式强化学习方法AB-MAPPER相比,DCAMAPF在离散初始化环境,阻塞率均值均约降低了6.91、4.97、3.56个百分点;在集中初始化环境下能更高效地避免发生阻塞,阻塞率均值均约降低了15.86、11.71、5.54个百分点,并减少占用的计算缓存。所提方法确保了路径规划的效率,适用于求解不同动态环境下的多机器人路径规划任务。

基于模仿学习和强化学习的启发式多智能体路径规划

多智能体路径规划(Multi-Agent Path Finding,MAPF)扩展到大型动态环境中是一个越来越有挑战的问题。现实世界中,环境动态变化往往需要实时重新规划路径。在部分可观察环境中,使用强化学习方法学习分散的策略解决MAPF问题表现出较大潜力。针对智能体之间如何学会合作和环境奖励稀疏问题,提出基于模仿学习和强化学习的启发式多智能体路径规划算法。实验表明,该方法在高密度障碍环境中具有较好的性能和扩展性。

人工智能背景下档案数字化管理路径分析

人工智能的应用有助于提高社会各领域的工作效率,然而对档案管理工作提出了新的要求。为促进档案数字化管理的发展,应该积极转变档案管理模式,充分利用人工智能技术。文章对档案数字化管理的基本概念进行了总结,从数据挖掘与信息提取、自然语言处理与语义理解等方面对人工智能技术在档案数字化管理中的应用进行了分析,并提出了档案数字化管理路径选择建议,从而更好地提高档案数字化管理水平。

Applications and Challenges of Deep Reinforcement Learning in Multi-robot Path Planning

With the rapid advancement of deep reinforcement learning(DRL)in multi-agent systems,a variety of practical application challenges and solutions in the direction of multi-agent deep reinforcement learning(MADRL)are surfacing.Path planning in a collision-free environment is essential for many robots to do tasks quickly and efficiently,and path planning for multiple robots using deep reinforcement learning is a new research area in the field of robotics and artificial intelligence.In this paper,we sort out the training methods for multi-robot path planning,as well as summarize the practical applications in the field of DRL-based multi-robot path planning based on the methods;finally,we suggest possible research directions for researchers.