Search

This comprehensive review focuses on the Autonomous Driving System (ADS), which aims to reduce human errors that are the reason for about 95% of car accidents. The ADS consists of six stages: sensors, perception, localization, assessment, path planning, and control. We explain the main state-of-the-art techniques used in each stage, analyzing 275 papers, with 162 specifically on path planning due to its complexity, NP-hard optimization nature, and pivotal role in ADS. This paper categorizes path planning techniques into three primary groups: traditional (graph-based, sampling-based, gradient-based, optimization-based, interpolation curve algorithms), machine and deep learning, and meta-heuristic optimization, detailing their advantages and drawbacks. Findings show that meta-heuristic optimization methods, representing 23% of our study, are preferred for being general problem solvers capable of handling complex problems. In addition, they have faster convergence and reduced risk of local minima. Machine and deep learning techniques, accounting for 25%, are favored for their learning capabilities and fast responses to known scenarios. The trend towards hybrid algorithms (27%) combines various methods, merging each algorithm's benefits and overcoming the other's drawbacks. Moreover, adaptive parameter tuning is crucial to enhance efficiency, applicability, and balancing the search capability. This review sheds light on the future of path planning in autonomous driving systems, helping to tackle current challenges and unlock the full capabilities of autonomous vehicles. [ABSTRACT FROM AUTHOR]

This paper presents a novel 3D path planning method for the underwater glider (UG) that incorporates adaptive segment strategy, motion parameters optimization, and an improved JADE algorithm. The method aims to generate an energy-efficient path by adapting to ocean currents and seabed topography and selecting favorable motion parameters. We establish an energy consumption model for a blended-wing-body UG, examining the influence of motion parameters and ocean currents on its performance. The proposed method encodes an energy-optimal gliding path through multiple path segments, each defined by a set of path points, pitch angles, and diving depths. The fitness function, based on energy consumption, guides the optimization process. To enhance the optimization, we present an improved JADE algorithm with multi-mutation strategies, which adaptively updates the mutation operation and mean crossover probability. Our method was assessed and compared with a classical UG path planning method on 6 test scenarios. Simulation results confirm that adaptive segments and motion parameter optimization contribute to better adaptation to ocean environments and reduced energy consumption. • A 3D path planning method for underwater gliders with adaptive segments and optimal motion parameters was proposed. • An energy consumption model for a blended wing body underwater glider was established. • An improved JADE algorithm with multi-mutation strategies was presented as an optimizer for UGAPP. • Significant improvements have been achieved in terms of energy savings for the underwater glider compared to a classical method. [ABSTRACT FROM AUTHOR]

Path planning is a key factor for the unmanned surface vehicle (USV) to achieve efficient navigation. In this paper, to solve the global path planning and obstacle avoidance problems for the USV, an improved Q-Learning algorithm called neural network smoothing and fast Q-Learning (NSFQ) is proposed. Three main improvement parts are composed of the proposed algorithm. Firstly, the radial basis function (RBF) neural network is combined with the Q-Learning algorithm to approximate the action value function Q, which improves the convergence speed of the Q-Learning algorithm. Secondly, to ensure that the planned path conforms to the maneuvering characteristics of the USV, the heading angle, motion characteristics, ship length, and safety of the USV are taken into account by the proposed algorithm. Based on these factors, the action space and reward function are optimized, the state space is reconstructed, and the safety threshold is proposed. Finally, a third-order Bezier curve is used to smooth the initial path, so that the USV can maintain its heading stability during navigation. Based on simulation results, the proposed NSFQ algorithm outperforms the A* and RRT algorithms in terms of evaluation indicators such as heading angle, angular velocity, path length, sailing time, and path smoothness. • An improved Q-Learning algorithm called neural network smoothing and fast Q-Learning (NSFQ) is proposed in this paper. • The heading angle, angular velocity, and other indicators of the USV are taken into account by this proposed algorithm. • A safety threshold is proposed to ensure the safety of the USV. • A third-order Bezier curve is used to smooth the initial path. [ABSTRACT FROM AUTHOR]

• This paper aims to enhance the optimality and rapidity of three dimensional IoDs. • Monte Carlo simulation is used to compare different CIPSO algorithms. • The proposed algorithm shows improvement in convergence speed and optimal solution. Drones flights have been investigated widely. In the presence of high density and complex missions, collision avoidance among swarm of drones and with environment obstacles becomes a challenging task and indispensable. This paper aims to enhance the optimality and rapidity of three dimensional IoD path generation by improving the particle swarm optimization (PSO) algorithm. The improvements include using chaos map logic to initialize the population of PSO. Also, adaptive mutation is utilized to balance local and global search. Then, the inactive particles are replaced by new fresh particles to push the solution toward global optimal. Furthermore, Monte Carlo simulation is carried out and the results are compared with slandered PSO and with recent work CIPSO. The results exhibit significant improvement in convergence speed as well as optimal solution which prove the ability of proposed method to generate safety path for IoD formation without collision with terrain obstacle and among drones. [ABSTRACT FROM AUTHOR]

Addressing the challenges of low convergence accuracy and stagnation at local optima in the application of the golden jackal optimizer (GJO) to mobile robot path planning, this paper proposes a hybrid strategy-based golden jackal optimizer (HGJO) algorithm. The improved algorithm employs a pre-decreasing slow nonlinear energy decay strategy to balance the global and local search capabilities. The roulette wheel selection algorithm and Lévy flight strategy are introduced into the position update of the GJO algorithm, so the proposed algorithm avoids stagnation at the local optimum. The HGJO algorithm is evaluated against some state-of-the-art optimizers on 23 benchmark functions and the CEC2021 benchmark function. It is also applied to ablation experiments for mobile robot path planning. The experimental results show that the HGJO algorithm improves the average path length in path planning by 0.21%, 82.4%, and 7.9% over the original algorithm in three different environments under 30 independent experiments. • A new energy decreasing method is proposed. • A roulette wheel selection strategy is introduced. • A new hybrid position updating strategy is proposed. [ABSTRACT FROM AUTHOR]

Artificial bee colony (ABC) is a prominent algorithm that offers great exploration capabilities among various meta-heuristic algorithms. However, its monotonous and one-dimensional search strategy limits its searching performance in the solving process. Thus, to address this issue, a Q-learning based multi-strategy integrated ABC algorithm (QMABC) is proposed. In the QMABC, multiple search strategies are proposed to utilize different individual experiences and search approaches for solution updates. Then, Q-learning is employed for strategy selection. In comparison to previous studies, this paper introduces more effective state and action configurations within the framework of Q-learning. To evaluate the performance of the QMABC, CEC 2017 benchmark functions are adopted to compare it to different meta-heuristic algorithms including ABC based and non-ABC based algorithms. Moreover, applications in path planning are implemented to further verify the effectiveness of the QMABC. Overall, it should be highlighted that the proposed QMABC demonstrates superiority in both numerical and practical experiments. • A Q-learning based multi-strategy integrated ABC algorithm is proposed. • Multiple strategies are introduced to the onlooker bee phase. • Q-learning is utilized to adaptively determine the most suitable strategy. • Novel state and action settings are designed in Q-learning framework. • Proposed algorithm shows superiority in numerical and practical experiments. [ABSTRACT FROM AUTHOR]

The increasing number of bridges in inland waterways has been continuously posing the potential for ship-bridge collision accidents. To reduce the probability of accidents in the inland bridge area and facilitate the safe passage of the autonomous ship, this paper proposes a path planning method with multiple vector fields, which comprehensively considers the characteristics of inland waters, hydrological characteristics, and meteorological factors. In this method, the navigational environmental factors affecting the path generation are divided into two parts, the static vector field, and the dynamic vector field, in the modeling part of the navigation environment. The static vector field is composed of the obstacle vector field and the channel vector field, and the dynamic vector field is constructed by the simulated wind field and currents field. The resulting synthetic vector field is used as input to the Anisotropic Fast Marching (AFM) algorithm to calculate the optimal path for the autonomous ship under influence of multiple factors. The complete algorithm has been tested and validated through three different scenarios and is evaluated according to four different evaluation criteria. The contribution of this work is to develop a path planning method that could incorporate external environmental influences and navigational risk into the path planning process. The research results of this paper can provide an important reference for the research on the path planning of autonomous ships in the inland bridge area. • The characteristic elements of inland bridge waters are considered in path planning. • The obstacle repulsion field, channel field and simulated wind field are generated by the traditional FM algorithm. • A multi-vector field mixing method is proposed to generate the optimal route with AFM method. [ABSTRACT FROM AUTHOR]

Path planning is an important and classical problem in theoretical research and practical applications. In the complex and hierarchical space scenarios, path planning faces more difficulties and challenges due to the structural particularity. Considering the directivity of paths in hierarchical spaces, it is more important to guarantee the fluency and efficiency of the paths in hierarchical spaces. In this paper, we introduce a path network planning problem from multi-source to multi-destination in hierarchical spaces, namely Balanced-Flow Path Network Planning (BF-PNP) problem, and prove its NP-completeness. To balance the flow rate among the layers in the space, we propose a batch scheduling algorithm with the objective of minimizing the scheduling time consumption. To evaluate the performance on efficiency and time complexity, we perform a series of simulations and the results indicate the advantages of the proposed algorithm. [ABSTRACT FROM AUTHOR]

In several applications, a robot moving from a start to a goal location is required to gather data along its path (e.g., a video feed in a monitoring scenario). The robot can have at its disposal only a limited amount of memory to store the collected data, in order to contain costs or to avoid that sensitive data fall into the hands of an attacker. This poses the need of periodically delivering the data to a Base Station (BS) through a deployed communication infrastructure that, in general, is not available everywhere. In this paper, we study this scenario by considering a variant of the shortest path problem (which we prove to be NP-hard) where the robot acquires information along its path, stores it into a limited memory buffer, and ensures that no information is lost by periodically communicating data to the BS. We present and evaluate an optimal exponential-time algorithm, an efficient feasibility test, and a polynomial-time heuristic algorithm. • A robot gathers data along its path with limited emory and restricted communication. • We study this scenario as a constrained variant of the shortest path problem. • We show that the problem is NP-hard and propose optimal and heuristic algorithms. [ABSTRACT FROM AUTHOR]

Path planning is essential for robots to efficiently execute jobs in challenging settings. In this paper, we propose a new algorithm, called potential function-based sampling heuristic optimal path planning considering congestion (CCPF-RRT*), extending the standard Rapidly-exploring Random Tree star (RRT*) to address the issues of slow convergence, high path cost, and how to plan suitable paths in the presence of congested regions in the environment. First, the CCPF-RRT* algorithm adds the artificial potential field to RRT*, which can drastically cut down on the number of iterations and speed up convergence. Second, a movement cost function that takes congestion intensity and path length into account when evaluating a connection between two path nodes is created. This function is then used to direct the growth of new nodes and the updating of parent nodes so that the algorithm takes congestion intensity and path length into account when generating paths. Third, in order to reduce the path cost, the algorithm establishes parent nodes for random nodes by combining the benefits of the F-RRT* algorithm. The movement cost function is added to the process of establishing parent nodes to optimize the path cost in order to prevent the creation of parent nodes that force the path to traverse through crowded areas. In experimental simulation results, the algorithm outperforms RRT*, Q-RRT*, PQ-RRT*, and F-RRT* not only in terms of initial solution and quick convergence speed, but is also able to design an ideal path with the lowest movement cost in a crowded environment using the movement cost function. [ABSTRACT FROM AUTHOR]

Unmanned Aerial Vehicles (UAVs) are frequently utilized for transferring and delivering. Dual- or multi-quadrotor cooperative transportation schemes are required for heavy loads. In this work, focusing on the path planning for a dual-quadrotor cooperative transport system, a unique artificial potential field-A*(APF-A*) algorithm is studied to fulfill the safe and effective cooperative suspension transport. APF-A* algorithm proposed the strategy of host-wingman cooperative transportation based on the APF theory, and optimizes the heuristic function by introducing the concept of repulsive force to maintain the quadrotor flying at a safe distance from the obstacle. In addition, APF-A* algorithm promises to increase search efficiency while identifying the optimal path, and it can reduce the swing angle motion of loads to enhance the security of transportation. The coordinated flight control and path planning of quadrotor UAVs are simulated in AirSim environment and tested in flight experiments. The results demonstrate that the algorithm is capable to plan safe and reliable paths, meanwhile changing formation and avoid collision when the wingman is close to obstacles. In comparison to the regular A* algorithm, the APF-A* algorithm proposed in the paper performs better in path planning for dual-quadrotor cooperative transport system, reducing the search time and the number of search grids by nearly 60% and 53.75%, respectively. [ABSTRACT FROM AUTHOR]

Mobile robot path planning refers to the design of the safely collision-free path with shortest distance and least time-consuming from the starting point to the end point by a mobile robot autonomously. In this paper, a systematic review of mobile robot path planning techniques is presented. Firstly, path planning is classified into global path planning and local path planning according to the mastery of environmental information. In the global path planning, environment modeling methods and path evaluation method are introduced. The methods of environment modeling include grid method, topology method, geometric feature method and mixed representation method. In the local path planning, we introduce the sensors commonly used in the detection environment, including laser radar and visual sensor. Next, according to the characteristics of algorithms, mobile robot path planning algorithms are divided into three categories: classical algorithms, bionic algorithms and artificial intelligence algorithms. Among the classical algorithms, we introduce the cell decomposition method, sampling based method, graph search algorithm, artificial potential field method and dynamic window method. In the algorithm based on bionics, we introduce genetic algorithm, ant colony algorithm, gray wolf algorithm, etc. in detail. In artificial intelligence algorithm, we introduce neural network algorithm and fuzzy logic. Finally, we compare the key technologies of mobile robot path planning in the form of graphs and charts based on the classification statistics of the collected literature to provide references for future research. [ABSTRACT FROM AUTHOR]

Automatic path planning is an essential aspect of unmanned aerial vehicle (UAV) autonomy. This paper presents a three dimensional path planning algorithm based on adaptive sensitivity decision operator combined with particle swarm optimization (PSO) technique. In the proposed method, an adaptive sensitivity decision area is constructed to overcome the defects of local optimal and slow convergence. By using this specified area, the potential particle locations with high probabilities are determined and other candidates are deleted to improve computational capacity. Then the searching space of particles is constrained in a limited boundary to avoid premature state. In addition, the searching accuracy is enhanced by the relative particle directivity from current location. The objective function is redesigned by taking into account the distance to destination and UAV self-constraints. To evaluate the path length, the paired-sample T-Test is performed and the straight line rate ( SLR ) index is introduced. In the two scenarios applied in this paper, our proposed method is 35.4 % , 21.6 % and 49.5 % better compared with other three tested optimization algorithms in the path cost on average. Correspondingly it is 9.6 % , 12.8 % , and 25.3 % better in SLR , which is capable of generating higher quality paths efficiently for UAVs. [ABSTRACT FROM AUTHOR]

This paper addresses problems of large planning time and cost uncertainty for informative path planning of a mobile sensor where the location of sensor deployment is different of that of an operational area. The first problem is that the cost has no term dependent on sensor state before arriving at the operational area and it causes large planning time. The information of the state of interest dissipates over time during the planning time and it degrades performance of sensing operation. The other problem is that the cost is dependent on the parameters to be estimated. To assess the cost, the target state in the future should be predicted by integrating the system model based on noisy initial estimate. The limitation of the informative path planning has a greater impact on performance in this specific problem. A strategy to cope with these problems is to devise a real-time path planning algorithm by using online optimization. The proposed algorithm is divided into two phases; determining the path to the boundary of the operational area and guiding the sensor by an informative potential field in the area. Detailed analysis on performance of the proposed algorithm compared to an optimal solution by nonlinear programming is given. The simulation results have demonstrated that the proposed algorithm can cope with performance degradation observed in the optimal solution. [ABSTRACT FROM AUTHOR]

Intelligent path planning is a significant tool for field of industrial robot. This field has attracted the attention of numerous researchers due to the great market demands, broad application prospects, and large potential development. Due to the limitation of neighborhood, the path search by the original A* algorithm is more likely to fail, and the solved path may contain too many local paths. In this study, an improved A* algorithm is proposed to solve the robot path planning problem. The first improvement of the advanced method is the local path between the current node and the goal node, which is planned before the next search in the neighborhood of the current node. And the local path will be adopted directly if it is safe and collisionless. The second advantage of this method is the utilization of post-processing stage to optimize the resulting path, by straightening the local path to reduce the number of local paths as well as the path length. In order to verify the theoretical advantages of the improved A* algorithm, a series of two-dimensional figures of the robot task was presented in this paper. In addition, some comparative experiments in the virtual and real robot manipulator platform are performed to examine the improved A* algorithm. Experimental results show that the search success rate of the improved A* algorithm is higher than the original A* algorithm, along with a shorter and smoother path could be obtained by the improved A* algorithm. Therefore, the success rate of robot path planning and the optimal extent of the robot path are effectively improved by the improved A* algorithm. [ABSTRACT FROM AUTHOR]

The paper presents a method of determining the optimal trajectory of the characteristic point belonging to the end effector of a parallel robot with six degrees of freedom type 6 R SS. The parallel robot is composed of a fixed plate and a mobile platform connected by six independent kinematic chains. Each of the six kinematic chains was part of one rotational actuating joint and two spherical joints. Based on the kinematic analysis, the motions of the end effector element were defined for manipulation operations using polynomial expressions of geometric parameters as time functions. By means of computational programs the polynomial variation of the motion parameters was determined. The data obtained were analysed on the basis of CAD programs through which the angular velocities of the actuating arms were determined when the end effector followed the trajectory described by the Hermite function. Using the same Hermite polynomials, two methods for optimizing the trajectory of the characteristic point were developed, the first intended to minimize its length and the second to minimize the runtime of the trajectory. [ABSTRACT FROM AUTHOR]

Natural or man-made disasters can cause different kinds of moving obstacles (e.g., fires, plumes, floods), which make some parts of the road network temporarily unavailable. After such incidents occur, responders have to go to different destinations to perform their tasks in the environment affected by the disaster. Therefore they need a path planner that is capable of dealing with such moving obstacles, as well as generating and coordinating their routes quickly and efficiently. In this paper, we present a novel approach for using a multi-agent system for navigating one or multiple responders to one or multiple destinations in the presence of moving obstacles. Our navigation system supports information collection from hazard simulations, spatio-temporal data processing and analysis, connection with a geo-database, and route generation in dynamic environments affected by disasters. We design and develop a set of software geospatial agents that assist emergency actors in dealing with the spatio-temporal data required for emergency navigation, based on their roles in the disaster response. One of the key components of the system is the path planning module, which combines the modified A* algorithm, insertion heuristics, and auction algorithm to calculate obstacle-avoiding routes for multiple responders with multiple destinations. A spatial data model is designed to support the storage of information about the tasks and routes produced during the disaster response. Our system has been validated using four navigation cases. Some preliminary results are presented in this paper and show the potential of the system for solving more navigation cases. [ABSTRACT FROM AUTHOR]

In this paper, the navigation system of the autonomous vehicle prototype Verdino is introduced. Two navigation levels are considered. In the first level, a trajectory is generated from the current position toward a goal that considers two different approaches. In the first, the minimum cost path is obtained using a classical approach (used for regular navigation). The second approach is a little more complex, relying on a set of precomputed primitives representing the motion model of the vehicle, which are used as part of an ARA⁎ algorithm in order to find the best trajectory. This trajectory consists of both forward and backward motion segments for complex maneuvers. In the second level, a local planner is in charge of computing the commands sent to the vehicle in order to follow the trajectory. A set of tentative local trajectories is computed in the Frenét space and scored using several factors, described in this paper. Some results for the two navigation levels are shown at the end of this document. For the global planner, several examples of the maneuvers obtained are shown and certain related factors are quantified and compared. As for the local planner, a study on the influence of the defined weights on the vehicle׳s final behavior is presented. Also, from these tests several configurations have been chosen and ranked according to two different proposed behaviors. The navigation system shown has been tested both in simulated and in real conditions, and the attached video shows the vehicle׳s real-world performance. [ABSTRACT FROM AUTHOR]

Recently, there has been growing interest in developing Autonomous Underwater Vehicle (AUV) to operate for longer mission durations as well as with higher levels of autonomy. This paper describes the current state of the art in methodologies to enable long range AUVs and provides a detailed literature review of some existing AUVs characterizing their operation endurance. Path planning is identified as the core and crucial components to improve AUV persistence. The aims of path optimization, path re-planning adapting to the dynamic environments, and cooperative path planning of multiple AUVs have received much attention from the research community. This paper presents a review of the main research works focusing on these three technology areas. The main objective of this paper is to present a comprehensive survey of shape and properties of the path and optimization techniques for path planning. These techniques and algorithms have been classified into different classes and their assumptions and drawbacks have been discussed. Finally, the paper discusses the AUV literature in general and highlights challenges that need to be addressed in developing AUVs with advanced autonomy and capable of operating for longer mission durations. [ABSTRACT FROM AUTHOR]

This paper focuses on the mobile robot path planning problem of optimizing the performance metrics of bidirectional A* algorithm in randomized two-dimensional map environments. An algorithm called direction constraints adaptive extended bidirectional A* (DCAE-BA*), which is an improvement of the traditional target dynamic bidirectional A* algorithm (TTD-BA*), is proposed to improve the performance metrics of the algorithm. Regarding the improvement, we propose the adaptive extension method and the direction-constrained optimal node extension method (DCONE). Simulation experiments were conducted for DCAE-BA*, TTD-BA* and traditional A* algorithm (A*) in a large number of random two-dimensional map environments. The simulation experimental scenarios consider four types of start and end point relative directions and three obstacle proportions to objectively and comprehensively evaluate the performance of the proposed algorithms. The results show that different scenarios have a significant impact on the algorithm performance metrics. Finally, the overall performance of the proposed algorithm is evaluated with a large number of experiments in "random" scenarios, and the results show that DCAE-BA* obtains significantly better search time for all three obstacle proportions, and better path length and number of expanded nodes for 10% and 25% obstacle proportions. The effectiveness of the proposed DCAE-BA* algorithm is demonstrated, which provides an essential reference for the path planning of mobile robots in a random 2D map environment. • DCAE-BA* is improved by adaptive extension and direction-constrained optimal node extension (DCONE). • The Start-End Dir and obstacle proportions have a significant impact on the algorithm metrics. • Overall, the DCAE-BA* has the highest computational efficiency for all three types of obstacle proportion. • DCAE-BA* optimizes the path length in the "diagonal" scenario most significantly. • As the proportion of obstacles increases, the metric optimization effect decreases. [ABSTRACT FROM AUTHOR]

In this paper, we propose an adaptive obstacle avoidance algorithm based on DDPG (Deep Deterministic Policy Gradient) and DWA (Dynamic-Window Approach) to study the obstacle avoidance problem of robots in complex continuous state space. First, the obstacle avoidance problem is converted into an optimal learning incentive problem, and the self-learning of the obstacle avoidance policy is realized based on DDPG; second, the DWA obstacle avoidance trajectory evaluation function is optimized using the DDPG reward incentive mechanism, and the Experience Replay mechanism; finally, the algorithm model is simulated. The experiments show that the model can significantly circumvent the deficiency of the DWA algorithm in limiting to the optimal local solution in a complex environment and solve the action output problem in the continuous velocity and turning angle value interval of the robot; through the trial and error interaction with the environment and the trajectory evaluation incentive feedback, the obstacle avoidance passing ability of the robot in a complex environment is improved. [Display omitted] • We propose an adaptive obstacle avoidance algorithm based on DDPG (Deep Deterministic Policy Gradient) and DWA (Dynamic Window Approach), named the DDPG-DWA. • The DDPG-DWA algorithm can solve the problem of action output in the continuous velocity and turning angle value range of the robot. • The DDPG-DWA algorithm can avoid the problem of DWA algorithm easily being limited to local obstacle avoidance optimal solutions in complex environments. • The model is suitable for path obstacle avoidance of intelligent agents in complex, narrow and irregular environments. [ABSTRACT FROM AUTHOR]

This paper presents a mission system and the therein implemented algorithms for path planning in a time-varying environment based on graph methods. The basic task of the introduced path planning algorithms is to find a time-optimal path from a defined start position to a goal position with consideration of the time-varying ocean current for an autonomous underwater vehicle (AUV). Building on this, additional practice-oriented considerations in planning are discussed in this paper. Such points are the discussion of possible methods to accelerate the algorithms and the determination of the optimal departure time. The solutions and algorithms presented in this paper are focused on path planning requirements for the AUV “SLOCUM Glider”. These algorithms are equally applicable to other AUVs or aerial mobile autonomous systems. [ABSTRACT FROM AUTHOR]

We consider the problem of finding an optimal manoeuvre that moves a car-like vehicle between two configurations in minimum time. We propose a two phase algorithm in which a path that joins the two points is first found by solving a geometric optimisation problem, and then the optimal manoeuvre is identified considering the system dynamics and its constraints. We make the assumption that the path is composed of a sequence of clothoids. This choice is justified by theoretical arguments, practical examples and by the existence of very efficient geometric algorithms for the computation of a path of this kind. The focus of the paper is on the computation of the optimal manoeuvre, for which we show a semi-analytical solution that can be produced in a few milliseconds on an embedded platform for a path made of one hundred segments. Our method is considerably faster than approaches based on pure numerical solutions, it is capable to detect when the optimal solution exists and, in this case, compute the optimal control. Finally, the method explicitly considers nonlinear dynamics, aerodynamic drag effect and bounds on the longitudinal and on the lateral acceleration. [ABSTRACT FROM AUTHOR]

Unmanned surface vehicles (USVs) have obtained increasing interests in recent decades. Because of the features of improved mission efficiency and decreased resource costs, applications of USVs can been seen in both civilian and naval areas. In order to efficiently and effectively achieve missions without any human intervention, a robust and intelligent navigation, guidance and control (NGC) system is vital for USV. This paper has therefore presented a novel NGC system designed for a USV named Springer . The system is developed by integrating multiple functional modules, which include a reliable navigation module that provides reliable position and heading information, a robust autopilot module enabling Springer tracking well the waypoints and an intelligent path planning module that is capable of generating feasible and practical waypoints. The path planning algorithm has been developed based upon the angle guidance fast marching square method, which is able to calculate the optimal path according to vehicle's motion constraints. The designed NGC system has been validated in both real field trials and computer based simulations proving that Springer USV is able to autonomously navigate in different maritime environments with the guidance of the NGC system. [ABSTRACT FROM AUTHOR]

Urban air mobility (UAM) has attracted the attention of aircraft manufacturers, air navigation service providers and governments in recent years. Preventing the conflict among urban aircraft is crucial to UAM traffic safety, which is a key in enabling large scale UAM operation. Pre-flight conflict-free path planning can provide a strategic layer in the maintenance of safety performance, thus becomes an important element in UAM. This paper aims at tackling conflict-free path planning problem for UAM operation with a consideration of four-dimensional airspace management. In the paper, we first introduce AirMatrix, previously developed by the team, and extend it as a four-dimensional airspace management concept. On the basis of AirMatrix, we formulate the shortest flight time path planning problem considering resolution of conflicts with both static and dynamic obstacles. A Conflict-Free A* (CFA*) algorithm is developed for planning four-dimensional paths based on first-come-first-served scheme. The algorithm contains a novel design of heuristic function as well as a conflict detection and resolution strategy. Numerical simulation was carried out using the building information in a typical urban area in Singapore. The results show that the algorithm can generate paths resolving a significant number of potential conflicts in airspace utilization, with acceptable computational time and flight delay. The findings of this study will provide references for stakeholders to support the development of UAM. [ABSTRACT FROM AUTHOR]

Aiming at the path planning problem for searching static target by autonomous underwater vehicles (AUVs) in ocean environment, this paper proposes a hierarchical method based on the maximum cumulative detection reward or search efficiency. First, the mission sea region is described in the form of target probability map, and the subregions with high search value are extracted by the method of expectation-maximization (EM). For multiple AUVs, we propose the bidirectional negotiation with biased min-consensus (BN-BMC) algorithm to determine the allocation and prioritization of subregions to be searched. On this basis, we utilize an adaptive oval spiral coverage (AOSC) strategy to plan the coverage path within each subregion, and take the Dubins path satisfying the AUV kinematic constraint as the transition path between subregions. Finally, the simulation results validate the advantage of our method. • This paper proposes a hierarchical method to solve the AUV path planning problem for target search in ocean environment. • The bidirectional negotiation with biased min-consensus (BN-BMC) theory is proposed to allocate and prioritize subregions. • The adaptive oval spiral coverage (AOSC) strategy is used to achieve the full coverage of an oval-shape subregion. [ABSTRACT FROM AUTHOR]

Integrating multiple features for autonomous flight of aircraft requires extensive research over wide categories, high-level of know-how, and experiences. To contribute to these issues, this paper treats the realizable integration techniques of the path planning, trajectory generation, and trajectory-tracking control for the mission autonomy of the aircraft. A collision-free path over the three-dimensional digital terrain is efficiently generated using the P-RRT* algorithm and optimized using the line-of-sight path optimizer proposed in this paper. After additional waypoints are inserted into the planned straight-line path segments, a flyable trajectory for the position and heading angle can be built using the spline trajectory generator with reference to the prescribed velocity distribution. Finally, the incremental backstepping-control design has been adopted to provide accurate trajectory-tracking control. The paper addresses in detail the underlying rationales of the present selection of each technique from the realizability point of view. The integrated designs are validated through simulation studies for a series of autonomous mission scenarios of the rotorcraft. The results show that the P-RRT* algorithm combined with the line-of-sight path optimizer can provide a fast and efficient solution for path planning. Also, the extremely accurate trajectory-tracking performance has been achieved by applying the incremental backstepping control to the flyable trajectory obtained using the spline trajectory generator. [ABSTRACT FROM AUTHOR]

To date, a large number of optimization algorithms have been presented for Autonomous Underwater Vehicle (AUV) path planning. However, little effort has been devoted to compare these techniques. In this paper, an quantum-behaved particle swarm optimization (QPSO) algorithm is introduced for solving the optimal path planning problem of an AUV operating in environments with ocean currents. An extensive study of the most important optimization techniques applied to optimize the trajectory for an AUV in several test scenarios is presented. Extensive Monte Carlo trials were also run to analyse the performance of these optimization techniques based on solution quality and stability. The weaknesses and strengths of each technique have been stated and the most appropriate algorithm for AUV path planning has been determined. [ABSTRACT FROM AUTHOR]

• The pose of the end-effector can be better controlled by IGPEF. • DGC can help solve the local minimum problem. • PRF can solve the issues that the robot can not reach the target nearby obstacles. • PDNN is used to solve the kinematics problem under safety constraints. • RTPVS is applied to prevent the accumulation of position errors. Safety and accuracy are essential for path planning in a surgical navigation system. In this paper, an improved path planning algorithm is proposed to increase the autonomous level of spine surgery robots for higher safety and accuracy. Firstly, the dynamic gravitational constant and piecewise repulsion function are adopted to improve the traditional Artificial Potential Field algorithm to solve the common issues of path planning, including local minimum, unable to reach the target near obstacles. To better control the pose of the end-effector in an operation space, the positions of the two endpoints of the end-effector are further constrained. Secondly, an improved Primal-Dual Neural Network with multiple constraints is proposed to minimize the joint angular velocity norm. The multiple constraints are formulated according to the planned path, the obstacle avoidance of the robot and the joint limits. Moreover, a real-time planned velocity scheme is applied to prevent the accumulation of position errors. The simulation results of the pedicle screw implantation demonstrate that the robot can find the collision-free trajectory and arrive at the target position in various complicated situations. More specifically, the error between two endpoints of the end-effector and the target pose is below 0.1 mm in reaching the surgical tool pose, while the maximum position error is around 0.05 mm when performing the planned path. Moreover, two experiments are conducted in the real-world to verify the proposed algorithm is effective in practice. [ABSTRACT FROM AUTHOR]

Unmanned combat aerial vehicle (UCAV) technology has to address many challenges in complex battlefield environments. To produce a safe and low-energy flying path, a UCAV requires many points to build a path that avoids threats, which increases the problem dimension, consumes more computational resources and makes the results unstable. To address this issue, this paper employs a new model known as double-layer coding (DLC) for path planning with unevenly distributed points to decrease the number of superfluous points on the path. Meanwhile, the RPSO algorithm, which introduces a novel strategy of rotating particles in high-dimensional space to search for targets, is proposed as an enhanced particle swarm optimization (PSO) algorithm. The proposed method effectively improves PSO ′ s exploration capacity. Furthermore, RPSO is employed to implement the double-layer coding model for path planning (DLCRPSO). The experimental results show that the proposed DLCRPSO method for path planning always produces feasible flight paths in complex environments. [Display omitted] • A double-layer coding model for path planning is established. • An improved PSO with a novel exploration strategy is proposed. • The superiority of the double-layer coding model used improved PSO is verified. [ABSTRACT FROM AUTHOR]

Abstract: The specific topic considered in this paper, which plays a crucial role in on orbit servicing (OOS), is the autonomous capture of a target by a satellite-mounted manipulator. In this context, the trajectory generation techniques available to date have been designed for a servicing satellite, the attitude and position of which are actively controlled. The innovation in our work is the development of a reactionless trajectory generation strategy by means of which we attempt to find manipulator paths which will intercept the target without affecting the attitude of the base, thus avoiding the need for attitude control of the base during the operation of the arm. This strategy is based on the reaction null space (RNS) method, originally proposed by Yoshida, which allows on-line path generation and which appears to be the most manageable for implementation within a trajectory generation algorithm. Four novel algorithms, in increasing order of complexity, have been developed and implemented in Matlab. The simulations carried out show that it is possible to devise a reactionless capture trajectory satisfying all the constraints considered in the paper, despite the complication that the use of the RNS equations implies. [Copyright &y& Elsevier]

Coordinating the motion of multiple mobile robots is one of the fundamental problems in robotics. The predominant algorithms for coordinating teams of robots are decoupled and prioritized, thereby avoiding combinatorially hard planning problems typically faced by centralized approaches. While these methods are very efficient, they have two major drawbacks. First, they are incomplete, i.e. they sometimes fail to find a solution even if one exists, and second, the resulting solutions are often not optimal. In this paper, we present a method for finding and optimizing priority schemes for such prioritized and decoupled planning techniques. Existing approaches apply a single priority scheme which makes them overly prone to failure in cases where valid solutions exist. By searching in the space of prioritization schemes, our approach overcomes this limitation. It performs a randomized search with hill-climbing to find solutions and to minimize the overall path length. To focus the search, our algorithm is guided by constraints generated from the task specification. To illustrate the appropriateness of this approach, this paper discusses experimental results obtained with real robots and through systematic robot simulation. The experimental results illustrate the superior performance of our approach, both in terms of efficiency of robot motion and in the ability to find valid plans. [ABSTRACT FROM AUTHOR]

This paper is concerned with a Minimum-Time Intercept Problem (MTIP), for which a Dubins vehicle is guided from a position with a prescribed initial heading angle to intercept a moving target in minimum time. Some geometric properties for the solution of the MTIP are presented, showing that the solution paths must lie in a sufficient family of 4 candidates. Necessary and sufficient conditions for optimality of each candidate are established. By employing the geometric properties, it is found that the 4 candidates are determined by the zeros of some real-valued functions when the target's velocity is constant. In order to compute all the 4 candidates, the derivatives of these real-valued functions are transformed to polynomials so that the extrema of those real-valued functions can be computed by standard polynomial solvers. This allows employing a simple bisection method to find all the 4 candidates. Since the MTIP with a constant target's velocity is equivalent to the path planning problem of Dubins vehicle in a constant drift field, developing such an algorithm also enables efficiently finding the shortest Dubins path in a constant drift field. Finally, some numerical examples are presented, demonstrating and verifying the developments of the paper. [ABSTRACT FROM AUTHOR]

• The MDA + RRT algorithms guarantee that planned path satisfies the constraint of angle. • Compared with other algorithms, this algorithm does not increase the computation amount. • The feasibility and optimization of MDA + RRT are preferable to the corresponding RRT. • This method is a universal method that can be associated with any kind of RRT algorithm. In this paper, a cable-driven hyper-redundant manipulator with 17 degrees of freedom is presented for narrow and complex environments firstly. Based on the mechanical structure, the MDA + RRT algorithms is proposed for path planning considering the maximum deflection angle of joint. First, the transformation relationship between the path parameters and manipulator parameters is obtained through the theorem of sine of triangles and two extreme points, which can convert limitation of the deflection angle of the joint to the limitation of the deflection angle of the path. Then, three corresponding improved algorithms are proposed: MDA-RRT, MDA-RRT*, MDA-QRRT* on the basis of the traditional RRT, RRT* and Q-RRT* algorithms. Finally, six algorithms are applied to plan the path of avoiding three different obstacles respectively by simulation. The results demonstrate that, three improved algorithms can guarantee that the planned path satisfies the constraint of deflection angle of joint without increasing the computational amount compared with the three traditional algorithms, only by limiting the selection range of the next random vertex. Among the six algorithms, the feasibility and optimization of the MDA-QRRT* algorithm are the best and the feasibility and optimization of the three improved algorithms are also better than the corresponding traditional algorithms. [ABSTRACT FROM AUTHOR]

This paper addresses the path planning problem for robotic applications using homotopy classes. These classes provide a topological description of how paths avoid obstacles, which is an added value to the path planning problem. Homotopy classes are generated and sorted according to a lower bound heuristic estimator using a method we developed. Then, the classes are used to constrain and guide path planning algorithms. Three different path planners are presented and compared: a graph-search algorithm called Homotopic A ∗ (HA ∗ ), a probabilistic sample-based algorithm called Homotopic RRT (HRRT), and a bug-based algorithm called Homotopic Bug (HBug). Our method has been tested in simulation and in an underwater bathymetric map to compute the trajectory of an Autonomous Underwater Vehicle (AUV). A comparison with well-known path planning algorithms has also been included. Results show that our homotopic path planners improve the quality of the solutions of their respective non-homotopic versions with similar computation time while keeping the topological constraints. [ABSTRACT FROM AUTHOR]

This paper aims to give an optimal path planning of a mobile robot in a known indoor environment. An algorithm based on deep learning, ray tracing algorithm, waiting rule, and Rapidly-exploring Random Tree is proposed to solve the problem of obstacle avoidance and path planning. Firstly, GoogLeNet is used to classify obstacles. Here, it helps to distinguish between static and dynamic obstacles. Secondly, for the static obstacle avoidance, the ray tracing algorithm is proposed to avoid the obstacles which are identified by GoogLeNet. And for the dynamic obstacle avoidance, this paper proposed a waiting rule for dynamic obstacle avoidance. Thirdly, the RRT method plans a path from the start point to the goal point. The novelty of this paper is that the type of obstacles is distinguished by deep learning, and the two different kinds of obstacles used ray tracing algorithm and waiting rule to avoid obstacles collision, respectively. In experimental results, rapidly-exploring random tree is compared with genetic algorithm, and particle swarm optimization method in static environment, and it is compared with artificial potential field approach in dynamic environment. Experiments are carried out in the two-dimensional environment and successfully applied to the path planning of mobile robots in multi-obstacles environment, and they prove the feasibility of the algorithm. [ABSTRACT FROM AUTHOR]

In order to solve the unmanned underwater vehicle two-dimensional autonomous path planning problem in the environment affected by ocean current and obstacles, this paper applies the improved Fireworks-Ant Colony Hybrid Algorithm to solve it. Firstly, a two-dimensional Lamb vortex ocean current environment model with randomly distributed obstacles is established, and the circular obstacle is equivalent to a square grid. Then, the mathematical model of path planning is established considering the energy consumption cost, navigation time cost and navigation distance cost. Finally, the improved fireworks-ant colony hybrid algorithm is applied to solve the nonlinear optimization problem, and this algorithm is compared with the basic ant colony algorithm for simulation experiments in the four different marine environments. The experimental results show that this algorithm can quickly find the global optimal solution, and the more complex the environment, the more obvious its advantages. The algorithm proposed in this paper provides a new way for autonomous path planning of underwater vehicles. [ABSTRACT FROM AUTHOR]

• Propose a sampling-based asymptotically optimal path planning algorithm. • The proposed algorithm guarantees a fast convergence rate. • Theoretical proof of asymptotic optimality and fast convergence rate is given. During the last decade, sampling-based algorithms for path planning have gained considerable attention. The RRT*, a variant of RRT (rapidly-exploring random trees), is of particular concern to researchers due to its asymptotic optimality. However, the limits of the slow convergence rate of RRT* makes it inefficient for applications. For the purposes of overcoming these limitations, this paper proposes a novel algorithm, PQ-RRT*, which combines the strengths of P-RRT* (potential functions based RRT*) and Quick-RRT*. PQ-RRT* guarantees a fast convergence to an optimal solution and generates a better initial solution. The asymptotic optimality and fast convergence of the proposed algorithm are proved in this paper. Comparisons of PQ-RRT* with P-RRT* and Quick-RRT* in four benchmarks verify the effectiveness of the proposed algorithm. [ABSTRACT FROM AUTHOR]

Most of the existing path planning algorithms require a prior global map. Although there have been some algorithms proposed for unknown environments, they can only deal with those which just have several hidden obstacles in a roughly known global map. In order to improve the efficiency of robot's path planning without prior global maps, this paper proposes a Convolutionally Evaluated Gradient First Search (CE-GFS) path planning algorithm. It allows the robot to collect environmental information and complete path planning simultaneously. Firstly, the Gradient First Search (GFS) algorithm is proposed based on the gradient score parameter, with which the conventional cost function is replaced. The GFS can adapt to any moving direction through the environmental information surrounding the mobile robot and computing the gradient score parameter. Secondly, CE-GFS path planning algorithm is proposed based on GFS and convolutional evaluation method. The CE-GFS helps the robots to evaluate the efficiency of the global path and get global perception ability, so that they are prevented from going astray, which can significantly improve the efficiency of path planning. Finally, several simulation tests and field tests have been carried out. The test results show that convolutional evaluation improves the efficiency of CE-GFS by 86.94% on average compared with GFS at the price of 0.18% decrease in path planning success rate. Moreover, the time cost of the proposed CE-GFS algorithm is 42.18% less than that of FAR-Planner in some special cases. • Our CE-GFS gets rid of this dependence on an exploration algorithm, and allows the robot to combine the exploration and path planning stages. • Cost functions in conventional grid map algorithms are replaced with gradient score in our algorithm, to make the robot more flexible. • Convolutional evaluation method is proposed to evaluate the efficiency of the global path through local information, which can prevent the robot from going astray. [ABSTRACT FROM AUTHOR]

This paper considers the unmanned aerial vehicle (UAV) global path planning as an optimization problem with multiple constraints and proposes an improved fireworks algorithm (FWA) and particle swarm optimization (PSO) cooperation algorithm to generate an optimal path. The objective function of the UAV flight path is modeled to have the shortest length satisfying strict multiple threat area constraints. The α constrained method using the level comparison strategy is integrated into both FWA and PSO to enhance their superior constraint-handling ability. To increase the population diversity, the whole population is divided to fireworks and particles, which perform search operation in parallel. A new mutation strategy in the fireworks is adopted to avoid falling into the local optimum. Information sharing mechanism between fireworks and particles is established to make the population achieve the excellent global optimization performance. Several numerical simulations are carried out and the results show that our proposed algorithm performs well in obtaining high quality solutions and handling constraints. [ABSTRACT FROM AUTHOR]

Abstract: Effective and practical collision avoidance manoeuvres through traffic are still one of the major problems hindering the development and adoption of a fully autonomous vessel. There have been studies on the subject but the majority only consider the traffic from a single vessel perspective while the others utilised stochastic based algorithms which are not suitable for marine navigation which demands consistency. This paper describes the development of a deterministic path planning algorithm that computes a practical and COLREGS compliant navigation path for vessels which are on a collision course. The algorithm was evaluated with a set of test cases, simulating various traffic scenarios. Different aspects of the algorithm, such as the output consistency from different perspectives, practicality of the navigation path, computational performance as well as future work, are discussed. [Copyright &y& Elsevier]

Abstract: The aim of this paper is to report the preliminary development of an automatic collision avoidance technique for unmanned marine craft based on standardised rules, COLREGs, defined by the International Maritime Organisation. It is noted that all marine surface vessels are required to adhere to COLREGs at all times in order to minimise or eliminate the risk of collisions. The approach presented is essentially a reactive path planning algorithm which provides feedback to the autopilot of an unmanned vessel or the human captain of a manned ship for steering the craft safely. The proposed strategy consists of waypoint guidance by line-of-sight coupled with a manual biasing scheme. This is applied to the dynamic model of an unmanned surface vehicle. A simple PID autopilot is incorporated to ensure that the vessel adheres to the generated seaway. It is shown through simulations that the resulting scheme is able to generate viable trajectories in the presence of both stationary and dynamic obstacles. Rules 8 and 14 of the COLREGs, which apply to the amount of manoeuvre and to a head-on scenario respectively are simulated. A comparison is also made with an offline or deliberative grid-based path planning algorithm which has been modified to generate COLREGs-compliant routes. [Copyright &y& Elsevier]

Abstract: Motion planning for multiple mobile robots must ensure the optimality of the path of each and every robot, as well as overall path optimality, which requires cooperation amongst robots. The paper proposes a solution to the problem, considering different source and goal of each robot. Each robot uses a grammar based genetic programming for figuring the optimal path in a maze-like map, while a master evolutionary algorithm caters to the needs of overall path optimality. Co-operation amongst the individual robots’ evolutionary algorithms ensures generation of overall optimal paths. The other feature of the algorithm includes local optimization using memory based lookup where optimal paths between various crosses in map are stored and regularly updated. Feature called wait for robot is used in place of conventionally used priority based techniques. Experiments are carried out with a number of maps, scenarios, and different robotic speeds. Experimental results confirm the usefulness of the algorithm in a variety of scenarios. [Copyright &y& Elsevier]

Abstract: This paper presents a path and speed planner for automated public transport vehicles in unstructured environments. Since efficiency and comfort are two of the key issues in promoting this kind of transportation system, they are dealt with explicitly in the proposed planning algorithm. To that end, a global path planner has been designed with bounded continuous curvature and bounded curvature derivative to ensure smooth driving. This will allow the public transport system to know a priori which is the shortest path within a selected area that guarantees lateral accelerations and steering wheel speeds below given pre-set thresholds. A closed-form speed profiler uses semantic information provided by the path planner to set a continuous velocity reference that takes into account not only bounds on lateral and longitudinal accelerations consistent with comfort, but also a bound on longitudinal jerk. The suitability of the above two features was compared to manual driving in a real instrumented public transport vehicle on a test track. [Copyright &y& Elsevier]

Abstract: In this paper, a practically viable approach for conflict free, coordinated motion planning of multiple robots is proposed. The presented approach is a two phase decoupled method that can provide the desired coordination among the participating robots in offline mode. In the first phase, the collision free path with respect to stationary obstacles for each robot is obtained by employing an A* algorithm. In the second phase, the coordination among multiple robots is achieved by resolving conflicts based on a path modification approach. The paths of conflicting robots are modified based on their position in a dynamically computed path modification sequence (PMS). To assess the effectiveness of the developed methodology, the coordination among robots is also achieved by different strategies such as fixed priority sequence allotment for motion of each robot, reduction in the velocities of joints of the robot, and introduction of delay in starting of each robot. The performance is assessed in terms of the length of path traversed by each robot, time taken by the robot to realize the task and computational time. The effectiveness of the proposed approach for multi-robot motion planning is demonstrated with two case studies that considered the tasks with three and four robots. The results obtained from realistic simulation of multi-robot environment demonstrate that the proposed approach assures rapid, concurrent and conflict free coordinated path planning for multiple robots. [Copyright &y& Elsevier]

Abstract: Space robotic systems are expected to play an increasingly important role in future space activities. Nevertheless, dynamics modeling and motion planning of a space robot are much more complex than those of a fixed-base robot, due to the dynamic coupling between the manipulator and its base. On the other hand, in order to assure the success of on-orbital missions, many experiments are required to verify the key algorithms on the ground before the space robot is launched. In this paper, the main research achievements on dynamics modeling, path planning, and ground verification are reviewed, and future studies are recommended. Firstly, we summarize the essential modeling concepts, and deduce the kinematics and dynamics equations of a space robot. Secondly, the main motion planning approaches are discussed. Then, different ground verification systems, including the air-bearing table, neutral buoyancy, airplane flying, free-falling motion, suspension system, and hybrid system, are introduced. Finally, the future research trends are forecasted. [Copyright &y& Elsevier]