Optimizing Connections:Applied Shortest Path Algorithms for MANETs

This study is trying to address the critical need for efficient routing in Mobile Ad Hoc Networks(MANETs)from dynamic topologies that pose great challenges because of the mobility of nodes.Themain objective was to delve into and refine the application of the Dijkstra’s algorithm in this context,a method conventionally esteemed for its efficiency in static networks.Thus,this paper has carried out a comparative theoretical analysis with the Bellman-Ford algorithm,considering adaptation to the dynamic network conditions that are typical for MANETs.This paper has shown through detailed algorithmic analysis that Dijkstra’s algorithm,when adapted for dynamic updates,yields a very workable solution to the problem of real-time routing in MANETs.The results indicate that with these changes,Dijkstra’s algorithm performs much better computationally and 30%better in routing optimization than Bellman-Ford when working with configurations of sparse networks.The theoretical framework adapted,with the adaptation of the Dijkstra’s algorithm for dynamically changing network topologies,is novel in this work and quite different from any traditional application.The adaptation should offer more efficient routing and less computational overhead,most apt in the limited resource environment of MANETs.Thus,from these findings,one may derive a conclusion that the proposed version of Dijkstra’s algorithm is the best and most feasible choice of the routing protocol for MANETs given all pertinent key performance and resource consumption indicators and further that the proposed method offers a marked improvement over traditional methods.This paper,therefore,operationalizes the theoretical model into practical scenarios and also further research with empirical simulations to understand more about its operational effectiveness.

An Improved Iterated Greedy Algorithm for Solving Rescue Robot Path Planning Problem with Limited Survival Time

Effective path planning is crucial for mobile robots to quickly reach rescue destination and complete rescue tasks in a post-disaster scenario.In this study,we investigated the post-disaster rescue path planning problem and modeled this problem as a variant of the travel salesman problem(TSP)with life-strength constraints.To address this problem,we proposed an improved iterated greedy(IIG)algorithm.First,a push-forward insertion heuristic(PFIH)strategy was employed to generate a high-quality initial solution.Second,a greedy-based insertion strategy was designed and used in the destruction-construction stage to increase the algorithm’s exploration ability.Furthermore,three problem-specific swap operators were developed to improve the algorithm’s exploitation ability.Additionally,an improved simulated annealing(SA)strategy was used as an acceptance criterion to effectively prevent the algorithm from falling into local optima.To verify the effectiveness of the proposed algorithm,the Solomon dataset was extended to generate 27 instances for simulation.Finally,the proposed IIG was compared with five state-of-the-art algorithms.The parameter analysiswas conducted using the design of experiments(DOE)Taguchi method,and the effectiveness analysis of each component has been verified one by one.Simulation results indicate that IIGoutperforms the compared algorithms in terms of the number of rescue survivors and convergence speed,proving the effectiveness of the proposed algorithm.

Research on Evacuation Path Planning Based on Improved Sparrow Search Algorithm

Reducing casualties and property losses through effective evacuation route planning has been a key focus for researchers in recent years.As part of this effort,an enhanced sparrow search algorithm(MSSA)was proposed.Firstly,the Golden Sine algorithm and a nonlinear weight factor optimization strategy were added in the discoverer position update stage of the SSA algorithm.Secondly,the Cauchy-Gaussian perturbation was applied to the optimal position of the SSA algorithm to improve its ability to jump out of local optima.Finally,the local search mechanism based on the mountain climbing method was incorporated into the local search stage of the SSA algorithm,improving its local search ability.To evaluate the effectiveness of the proposed algorithm,the Whale Algorithm,Gray Wolf Algorithm,Improved Gray Wolf Algorithm,Sparrow Search Algorithm,and MSSA Algorithm were employed to solve various test functions.The accuracy and convergence speed of each algorithm were then compared and analyzed.The results indicate that the MSSA algorithm has superior solving ability and stability compared to other algorithms.To further validate the enhanced algorithm’s capabilities for path planning,evacuation experiments were conducted using different maps featuring various obstacle types.Additionally,a multi-exit evacuation scenario was constructed according to the actual building environment of a teaching building.Both the sparrow search algorithm and MSSA algorithm were employed in the simulation experiment for multiexit evacuation path planning.The findings demonstrate that the MSSA algorithm outperforms the comparison algorithm,showcasing its greater advantages and higher application potential.

Improving path planning efficiency for underwater gravity-aided navigation based on a new depth sorting fast search algorithm

This study focuses on the improvement of path planning efficiency for underwater gravity-aided navigation.Firstly,a Depth Sorting Fast Search(DSFS)algorithm was proposed to improve the planning speed of the Quick Rapidly-exploring Random Trees*(Q-RRT*)algorithm.A cost inequality relationship between an ancestor and its descendants was derived,and the ancestors were filtered accordingly.Secondly,the underwater gravity-aided navigation path planning system was designed based on the DSFS algorithm,taking into account the fitness,safety,and asymptotic optimality of the routes,according to the gravity suitability distribution of the navigation space.Finally,experimental comparisons of the computing performance of the ChooseParent procedure,the Rewire procedure,and the combination of the two procedures for Q-RRT*and DSFS were conducted under the same planning environment and parameter conditions,respectively.The results showed that the computational efficiency of the DSFS algorithm was improved by about 1.2 times compared with the Q-RRT*algorithm while ensuring correct computational results.

Path Planning for Robotic Arms Based on an Improved RRT Algorithm

The burgeoning robotics industry has catalyzed significant strides in the development and deployment of industrial and service robotic arms, positioning path planning as a pivotal facet for augmenting their operational safety and efficiency. Existing path planning algorithms, while capable of delineating feasible trajectories, often fall short of achieving optimality, particularly concerning path length, search duration, and success likelihood. This study introduces an enhanced Rapidly-Exploring Random Tree (RRT) algorithm, meticulously designed to rectify the issues of node redundancy and the compromised path quality endemic to conventional RRT approaches. Through the integration of an adaptive pruning mechanism and a dynamic elliptical search strategy within the Informed RRT* framework, our algorithm efficiently refines the search tree by discarding branches that surpass the cost of the optimal path, thereby refining the search space and significantly boosting efficiency. Extensive comparative analysis across both two-dimensional and three-dimensional simulation settings underscores the algorithm’s proficiency in markedly improving path precision and search velocity, signifying a breakthrough in the domain of robotic arm path planning.

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.

Path planning in uncertain environment by using firefly algorithm

Autonomous mobile robot navigation is one of the most emerging areas of research by using swarm intelligence. Path planning and obstacle avoidance are most researched current topics like navigational challenges for mobile robot. The paper presents application and implementation of Firefly Algorithm(FA)for Mobile Robot Navigation(MRN) in uncertain environment. The uncertainty is defined over the changing environmental condition from static to dynamic. The attraction of one firefly towards the other firefly due to variation of their brightness is the key concept of the proposed study. The proposed controller efficiently explores the environment and improves the global search in less number of iterations and hence it can be easily implemented for real time obstacle avoidance especially for dynamic environment. It solves the challenges of navigation, minimizes the computational calculations, and avoids random moving of fireflies. The performance of proposed controller is better in terms of path optimality when compared to other intelligent navigational approaches.

Algorithm for Low Altitude Penetration Aircraft Path Planning with Improved Ant Colony Algorithm

The ant colony algorithm is a new class of population basic algorithm. The path planning is realized by the use of ant colony algorithm when the plane executes the low altitude penetration, which provides a new method for the path planning. In the paper the traditional ant colony algorithm is improved, and measures of keeping optimization, adaptively selecting and adaptively adjusting are applied, by which better path at higher convergence speed can be found. Finally the algorithm is implemented with computer simulation and preferable results are obtained.

Efficient AUV Path Planning in Time-Variant Underwater Environment Using Differential Evolution Algorithm

Robust and efficient AUV path planning is a key element for persistence AUV maneuvering in variable underwater environments. To develop such a path planning system, in this study, differential evolution(DE) algorithm is employed. The performance of the DE-based planner in generating time-efficient paths to direct the AUV from its initial conditions to the target of interest is investigated within a complexed 3D underwater environment incorporated with turbulent current vector fields, coastal area,islands, and static/dynamic obstacles. The results of simulations indicate the inherent efficiency of the DE-based path planner as it is capable of extracting feasible areas of a real map to determine the allowed spaces for the vehicle deployment while coping undesired current disturbances, exploiting desirable currents, and avoiding collision boundaries in directing the vehicle to its destination. The results are implementable for a realistic scenario and on-board real AUV as the DE planner satisfies all vehicular and environmental constraints while minimizing the travel time/distance, in a computationally efficient manner.

AN OPTIMUM VEHICULAR PATH ALGORITHM FOR TRAFFIC NETWORK BASED ON HIERARCHICAL SPATIAL REASONING

Human beings’ intellection is the characteristic of a distinct hierarchy and can be taken to construct a heuristic in the shortest path algorithms.It is detailed in this paper how to utilize the hierarchical reasoning on the basis of greedy and directional strategy to establish a spatial heuristic,so as to improve running efficiency and suitability of shortest path algorithm for traffic network.The authors divide urban traffic network into three hierarchies and set forward a new node hierarchy division rule to avoid the unreliable solution of shortest path.It is argued that the shortest path,no matter distance shortest or time shortest,is usually not the favorite of drivers in practice.Some factors difficult to expect or quantify influence the drivers’ choice greatly.It makes the drivers prefer choosing a less shortest,but more reliable or flexible path to travel on.The presented optimum path algorithm,in addition to the improvement of the running efficiency of shortest path algorithms up to several times,reduces the emergence of those factors,conforms to the intellection characteristic of human beings,and is more easily accepted by drivers.Moreover,it does not require the completeness of networks in the lowest hierarchy and the applicability and fault tolerance of the algorithm have improved.The experiment result shows the advantages of the presented algorithm.The authors argued that the algorithm has great potential application for navigation systems of large_scale traffic networks.

Improved Ant Colony-Genetic Algorithm for Information Transmission Path Optimization in Remanufacturing Service System

The information transmission path optimization(ITPO) can often a ect the e ciency and accuracy of remanufactur?ing service. However, there is a greater degree of uncertainty and complexity in information transmission of remanu?facturing service system, which leads to a critical need for designing planning models to deal with this added uncer?tainty and complexity. In this paper, a three?dimensional(3D) model of remanufacturing service information network for information transmission is developed, which combines the physic coordinate and the transmitted properties of all the devices in the remanufacturing service system. In order to solve the basic ITPO in the 3D model, an improved 3D ant colony algorithm(Improved AC) was put forward. Moreover, to further improve the operation e ciency of the algorithm, an improved ant colony?genetic algorithm(AC?GA) that combines the improved AC and genetic algorithm was developed. In addition, by taking the transmission of remanufacturing service demand information of certain roller as example, the e ectiveness of AC?GA algorithm was analyzed and compared with that of improved AC, and the results demonstrated that AC?GA algorithm was superior to AC algorithm in aspects of information transmission delay, information transmission cost, and rate of information loss.

Global optimal path planning for mobile robot based onimproved Dijkstra algorithm and ant system algorithm

A novel method of global optimal path planning for mobile robot was proposed based on the improved Dijkstra algorithm and ant system algorithm. This method includes three steps: the first step is adopting the MAKLINK graph theory to establish the free space model of the mobile robot, the second step is adopting the improved Dijkstra algorithm to find out a sub-optimal collision-free path, and the third step is using the ant system algorithm to adjust and optimize the location of the sub-optimal path so as to generate the global optimal path for the mobile robot. The computer simulation experiment was carried out and the results show that this method is correct and effective. The comparison of the results confirms that the proposed method is better than the hybrid genetic algorithm in the global optimal path planning.

Path Planning of Continuum Robot Based on a New Improved Particle Swarm Optimization Algorithm

Continuum robot is a new type of biomimetic robot,which realizes the motion by bending some parts of its body.So its path planning becomes more difficult even compared with hyper-redundant robots.In this paper a circular arc spline interpolating method is proposed for the robot shape description,and a new two-stage position-selectable-updating particle swarm optimization(TPPSO)algorithm is put forward to solve this path planning problem.The algorithm decomposes the standard PSO velocity’s single-step updating formula into twostage multi-point updating,specifically adopting three points as candidates and selecting the best one as the updated position in the first half stage,and similarly taking seven points as candidates and selecting the best one as the final position in the last half stage.This scheme refines and widens each particle’s searching trajectory,increases the updating speed of the individual best,and improves the converging speed and precision.Aiming at the optimization objective to minimize the sum of all the motion displacements of every segmental points and all the axial stretching or contracting displacements of every segment,the TPPSO algorithm is used to solve the path planning problem.The detailed solution procedure is presented.Numerical examples of five path planning cases show that the proposed algorithm is simple,robust,and efficient.

Path Planning Method Based on D^(*) lite Algorithm for Unmanned Surface Vehicles in Complex Environments

In recent decades,path planning for unmanned surface vehicles(USVs)in complex environments,such as harbours and coastlines,has become an important concern.The existing algorithms for real-time path planning for USVs are either too slow at replanning or unreliable in changing environments with multiple dynamic obstacles.In this study,we developed a novel path planning method based on the D^(*) lite algorithm for real-time path planning of USVs in complex environments.The proposed method has the following advantages:(1)the computational time for replanning is reduced significantly owing to the use of an incremental algorithm and a new method for modelling dynamic obstacles;(2)a constrained artificial potential field method is employed to enhance the safety of the planned paths;and(3)the method is practical in terms of vehicle performance.The performance of the proposed method was evaluated through simulations and compared with those of existing algorithms.The simulation results confirmed the efficiency of the method for real-time path planning of USVs in complex environments.

Improved Dijkstra Algorithm for Mobile Robot Path Planning and Obstacle Avoidance

Optimal path planning avoiding obstacles is among the most attractive applications of mobile robots(MRs)in both research and education.In this paper,an optimal collision-free algorithm is designed and implemented practically based on an improved Dijkstra algorithm.To achieve this research objectives,first,the MR obstacle-free environment is modeled as a diagraph including nodes,edges and weights.Second,Dijkstra algorithm is used offline to generate the shortest path driving the MR from a starting point to a target point.During its movement,the robot should follow the previously obtained path and stop at each node to test if there is an obstacle between the current node and the immediately following node.For this aim,the MR was equipped with an ultrasonic sensor used as obstacle detector.If an obstacle is found,the MR updates its diagraph by excluding the corresponding node.Then,Dijkstra algorithm runs on the modified diagraph.This procedure is repeated until reaching the target point.To verify the efficiency of the proposed approach,a simulation was carried out on a hand-made MR and an environment including 9 nodes,19 edges and 2 obstacles.The obtained optimal path avoiding obstacles has been transferred into motion control and implemented practically using line tracking sensors.This study has shown that the improved Dijkstra algorithm can efficiently solve optimal path planning in environments including obstacles and that STEAM-based MRs are efficient cost-effective tools to practically implement the designed algorithm.

Two-Dimension Path Planning Method Based on Improved Ant Colony Algorithm

Nowadays, path planning has become an important field of research focus. Considering that the ant colony algorithm has numerous advantages such as the distributed computing and the characteristics of heuristic search, how to combine the algorithm with two-dimension path planning effectively is much important. In this paper, an improved ant colony algorithm is used in resolving this path planning problem, which can improve convergence rate by using this improved algorithm. MAKLINK graph is adopted to establish the two-dimensional space model at first, after that the Dijkstra algorithm is selected as the initial planning algorithm to get an initial path, immediately following, optimizing the select parameters relating on the ant colony algorithm and its improved algorithm. After making the initial parameter, the authors plan out an optimal path from start to finish in a known environment through ant colony algorithm and its improved algorithm. Finally, Matlab is applied as software tool for coding and simulation validation. Numerical experiments show that the improved algorithm can play a more appropriate path planning than the origin algorithm in the completely observable.

Path planning based on sliding window and variant A* algorithm for quadruped robot

In order to improve the adaptability of the quadruped robot in complex environments,a path planning method based on sliding window and variant A* algorithm for quadruped robot is presented. To improve the path planning efficiency and robot security,an incremental A* search algorithm( IA*) and the A* algorithm having obstacle grids extending( EA*) are proposed respectively. The IA* algorithm firstly searches an optimal path based on A* algorithm,then a new route from the current path to the new goal projection is added to generate a suboptimum route incrementally. In comparison with traditional method solving path planning problem from scratch,the IA* enables the robot to plan path more efficiently. EA* extends the obstacle by means of increasing grid g-value,which makes the route far away from the obstacle and avoids blocking the narrow passage. To navigate the robot running smoothly,a quadratic B-spline interpolation is applied to smooth the path.Simulation results illustrate that the IA* algorithm can increase the re-planning efficiency more than 5 times and demonstrate the effectiveness of the EA* algorithm.

Robot Global Path Planning Based on an Improved Ant Colony Algorithm

Aiming at the disadvantages of the basic ant colony algorithm, this paper proposes an improved ant colony algorithm for robot global path planning. First, adjust the pheromone evaporation rate dynamically to enhance the global search ability and convergence speed, and then modify the heuristic function to improve the state transition probabilities in order to find the optimal solution as quickly as possible;and finally change the pheromone update strategy to avoid premature by strengthening pheromone on the optimal path and limiting pheromone level. Simulation results verify the effectiveness of the improved algorithm.

A Novel Improved Bat Algorithm in UAV Path Planning

Path planning algorithm is the key point to UAV path planning scenario.Many traditional path planning methods still suffer from low convergence rate and insufficient robustness.In this paper,three main methods are contributed to solving these problems.First,the improved artificial potential field(APF)method is adopted to accelerate the convergence process of the bat’s position update.Second,the optimal success rate strategy is proposed to improve the adaptive inertia weight of bat algorithm.Third chaos strategy is proposed to avoid falling into a local optimum.Compared with standard APF and chaos strategy in UAV path planning scenarios,the improved algorithm CPFIBA(The improved artificial potential field method combined with chaotic bat algorithm,CPFIBA)significantly increases the success rate of finding suitable planning path and decrease the convergence time.Simulation results show that the proposed algorithm also has great robustness for processing with path planning problems.Meanwhile,it overcomes the shortcomings of the traditional meta-heuristic algorithms,as their convergence process is the potential to fall into a local optimum.From the simulation,we can see also obverse that the proposed CPFIBA provides better performance than BA and DEBA in problems of UAV path planning.

Application of GA, PSO, and ACO Algorithms to Path Planning of Autonomous Underwater Vehicles

In this paper, an underwater vehicle was modeled with six dimensional nonlinear equations of motion, controlled by DC motors in all degrees of freedom. Near-optimal trajectories in an energetic environment for underwater vehicles were computed using a nnmerical solution of a nonlinear optimal control problem （NOCP）. An energy performance index as a cost function, which should be minimized, was defmed. The resulting problem was a two-point boundary value problem （TPBVP）. A genetic algorithm （GA）, particle swarm optimization （PSO）, and ant colony optimization （ACO） algorithms were applied to solve the resulting TPBVP. Applying an Euler-Lagrange equation to the NOCP, a conjugate gradient penalty method was also adopted to solve the TPBVP. The problem of energetic environments, involving some energy sources, was discussed. Some near-optimal paths were found using a GA, PSO, and ACO algorithms. Finally, the problem of collision avoidance in an energetic environment was also taken into account.