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...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.展开更多
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 pla...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.展开更多
To address the shortcomings of traditional Genetic Algorithm (GA) in multi-agent path planning, such as prolonged planning time, slow convergence, and solution instability, this paper proposes an Asynchronous Genetic ...To address the shortcomings of traditional Genetic Algorithm (GA) in multi-agent path planning, such as prolonged planning time, slow convergence, and solution instability, this paper proposes an Asynchronous Genetic Algorithm (AGA) to solve multi-agent path planning problems effectively. To enhance the real-time performance and computational efficiency of Multi-Agent Systems (MAS) in path planning, the AGA incorporates an Equal-Size Clustering Algorithm (ESCA) based on the K-means clustering method. The ESCA divides the primary task evenly into a series of subtasks, thereby reducing the gene length in the subsequent GA process. The algorithm then employs GA to solve each subtask sequentially. To evaluate the effectiveness of the proposed method, a simulation program was designed to perform path planning for 100 trajectories, and the results were compared with those of State-Of-The-Art (SOTA) methods. The simulation results demonstrate that, although the solutions provided by AGA are suboptimal, it exhibits significant advantages in terms of execution speed and solution stability compared to other algorithms.展开更多
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 factor...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.展开更多
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 ...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.展开更多
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 an...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.展开更多
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 a...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.展开更多
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 t...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.展开更多
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 ...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.展开更多
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...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.展开更多
Multiple UAVs cooperative target search has been widely used in various environments,such as emergency rescue and traffic monitoring.However,uncertain communication network among UAVs exhibits unstable links and rapid...Multiple UAVs cooperative target search has been widely used in various environments,such as emergency rescue and traffic monitoring.However,uncertain communication network among UAVs exhibits unstable links and rapid topological fluctuations due to mission complexity and unpredictable environmental states.This limitation hinders timely information sharing and insightful path decisions for UAVs,resulting in inefficient or even failed collaborative search.Aiming at this issue,this paper proposes a multi-UAV cooperative search strategy by developing a real-time trajectory decision that incorporates autonomous connectivity to reinforce multi-UAV collaboration and achieve search acceleration in uncertain search environments.Specifically,an autonomous connectivity strategy based on node cognitive information and network states is introduced to enable effective message transmission and adapt to the dynamic network environment.Based on the fused information,we formalize the trajectory planning as a multiobjective optimization problem by jointly considering search performance and UAV energy harnessing.A multi-agent deep reinforcement learning based algorithm is proposed to solve it,where the reward-guided real-time path is determined to achieve an energyefficient search.Finally,extensive experimental results show that the proposed algorithm outperforms existing works in terms of average search rate and coverage rate with reduced energy consumption under uncertain search environments.展开更多
基金Aeronautical Science Foundation of China(No.20220001057001)。
文摘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.
基金supported by National Natural Science Foundation of China(No.62073212)Shanghai Science and Technology Commission(No.23ZR1426600).
文摘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.
文摘To address the shortcomings of traditional Genetic Algorithm (GA) in multi-agent path planning, such as prolonged planning time, slow convergence, and solution instability, this paper proposes an Asynchronous Genetic Algorithm (AGA) to solve multi-agent path planning problems effectively. To enhance the real-time performance and computational efficiency of Multi-Agent Systems (MAS) in path planning, the AGA incorporates an Equal-Size Clustering Algorithm (ESCA) based on the K-means clustering method. The ESCA divides the primary task evenly into a series of subtasks, thereby reducing the gene length in the subsequent GA process. The algorithm then employs GA to solve each subtask sequentially. To evaluate the effectiveness of the proposed method, a simulation program was designed to perform path planning for 100 trajectories, and the results were compared with those of State-Of-The-Art (SOTA) methods. The simulation results demonstrate that, although the solutions provided by AGA are suboptimal, it exhibits significant advantages in terms of execution speed and solution stability compared to other algorithms.
基金National Natural Science Foundation of China(Nos.61673262 and 50779033)National GF Basic Research Program(No.JCKY2021110B134)Fundamental Research Funds for the Central Universities。
文摘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.
基金supported by Bright Dream Robotics and the HKUSTBDR Joint Research Institute Funding Scheme under Project HBJRI-FTP-005(Automated 3D Reconstruction using Robot-mounted 360-Degree Camera with Visible Light Positioning Technology for Building Information Modelling Applications,OKT22EG06).
文摘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.
基金The National Key Technology R&D Program of China during the 11th Five Year Plan Period(No.2008BAJ11B01)
文摘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.
基金the National Natural Science Foundation of China(No.51577112,51575328)Science and Technology Commission of Shanghai Municipality Project(No.16511108600).
文摘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.
文摘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.
基金supported by the National Natural Science Foundation of China (61903036, 61822304)Shanghai Municipal Science and Technology Major Project (2021SHZDZX0100)。
文摘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.
基金Supported by the National Key Research and Development Program of China(No.2020YFC1807904).
文摘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.
基金supported by National Natural Science Foundation of China(No.62202449 and No.62472410)National Key Research and Development Program of China(2021YFB2900102)。
文摘Multiple UAVs cooperative target search has been widely used in various environments,such as emergency rescue and traffic monitoring.However,uncertain communication network among UAVs exhibits unstable links and rapid topological fluctuations due to mission complexity and unpredictable environmental states.This limitation hinders timely information sharing and insightful path decisions for UAVs,resulting in inefficient or even failed collaborative search.Aiming at this issue,this paper proposes a multi-UAV cooperative search strategy by developing a real-time trajectory decision that incorporates autonomous connectivity to reinforce multi-UAV collaboration and achieve search acceleration in uncertain search environments.Specifically,an autonomous connectivity strategy based on node cognitive information and network states is introduced to enable effective message transmission and adapt to the dynamic network environment.Based on the fused information,we formalize the trajectory planning as a multiobjective optimization problem by jointly considering search performance and UAV energy harnessing.A multi-agent deep reinforcement learning based algorithm is proposed to solve it,where the reward-guided real-time path is determined to achieve an energyefficient search.Finally,extensive experimental results show that the proposed algorithm outperforms existing works in terms of average search rate and coverage rate with reduced energy consumption under uncertain search environments.
