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.

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.

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.

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.

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.

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.

Hybrid Algorithm-Driven Smart Logistics Optimization in IoT-Based Cyber-Physical Systems

Effectively managing complex logistics data is essential for development sustainability and growth,especially in optimizing distribution routes.This article addresses the limitations of current logistics path optimization methods,such as inefficiencies and high operational costs.To overcome these drawbacks,we introduce the Hybrid Firefly-Spotted Hyena Optimization(HFSHO)algorithm,a novel approach that combines the rapid exploration and global search abilities of the Firefly Algorithm(FO)with the localized search and region-exploitation skills of the Spotted Hyena Optimization Algorithm(SHO).HFSHO aims to improve logistics path optimization and reduce operational costs.The algorithm’s effectiveness is systematically assessed through rigorous comparative analyses with established algorithms like the Ant Colony Algorithm(ACO),Cuckoo Search Algorithm(CSA)and Jaya Algo-rithm(JA).The evaluation also employs benchmarking methodologies using standardized function sets covering diverse objective functions,including Schwefel’s,Rastrigin,Ackley,Sphere and the ZDT and DTLZ Function suite.HFSHO outperforms these algorithms,achieving a minimum path distance of 546 units,highlighting its prowess in logistics path optimization.This comprehensive evaluation authenticates HFSHO’s exceptional performance across various logistic optimization scenarios.These findings emphasize the critical significance of selecting an appropriate algorithm for logistics path navigation,with HFSHO emerging as an efficient choice.Through the synergistic use of FO and SHO,HFSHO achieves a 15%improvement in convergence,heightened operational efficiency and substantial cost reductions in logistics operations.It presents a promising solution for optimizing logistics paths,offering logistics planners and decision-makers valuable insights and contributing substantively to sustainable sectoral growth.

Effective rural electrification via optimal network: Optimal path-finding in highly anisotropic search space using multiplier-accelerated A* algorithm

United Nations’7th Sustainable Development Goal envisions the availability of modern energy for everyone by 2030.While the progress has been satisfactory in the last few years,further rural electrification is increasingly challenging.The current mainstream approach of electrifying villages individually is becoming cost-ineffective due to uncertainties in both resource availability and energy demand for small,difficult-to-reach,residences.A networked rural electrification model,i.e.a cost-optimized network connecting villages and generation facilities,could improve resources utilization,reliability and flexibility.However,determining optimal paths with common search algorithms is extremely inefficient due to complex topographic features of rural areas.This work develops and applies an artificial intelligence search method to efficiently route inter-village power connections in the common rural electrification situation where substantial topological variations exist.The method is evolved from the canonical A*algorithm.Results compare favorably with optimal A*results,at significantly reduced computational effort.Furthermore,users can adaptively trade-off between computation speed and optimality and hence quickly evaluate sites and configurations at reasonable accuracy,which is impossible with classical methods.

Flexible networked rural electrification using levelized interpolative genetic algorithm

Networked rural electrification is an alternative approach to accelerate rural electrification.Using satellite photos and GIS tools,an electrical distribution network is used to connect villages and properly located generation facilities together to reduce electrification cost.To design the network,optimal paths connecting all node-pairs are identified,followed by finding a network topology that minimizes cost.Earlier work has illustrated that A*(A-star,an optimal path-finding algorithm)is inefficient for this application due to the complex topography in rural areas.The multiplier-accelerated A*(MAA*)algorithm overcomes key performance issues,but,like A*,produces only one path connecting each node-pair.Relying on one path increases project risk because adverse conditions,such as inaccurate GIS estimation,unexpected soil conditions,land-rights disputes,political issues,etc.can occur during implementation.In this paper,a hybrid path-finding method combining genetic algorithm and A*/MAA*algorithm is proposed.The proposed method provides a family of near-optimal paths instead of a single optimal path for routing.A family of paths allows a project implementer to quickly adapt to unexpected situations as new information becomes available,and flexibly change network topology before or during implementation with minimal impact on project cost.