Improved RRT*-Connect Manipulator Path Planning in a Multi-Obstacle Narrow Environment

This paper proposes an improved RRT*-Connect algorithm (IRRT*-Connect) for robotic arm path planning in narrow environments with multiple obstacles. A heuristic sampling strategy is adopted with the integration of the ellipsoidal subset sampling and goal-biased sampling strategies, which can continuously compress the sampling space to enhance the sampling efficiency. During the node expansion process, an adaptive step-size method is introduced to dynamically adjust the step size based on the obstacle information, while a node rejection strategy is used to accelerate the search process so as to generate a near-optimal collision-free path. A pruning optimization strategy is also proposed to eliminate the redundant nodes from the path. Furthermore, a cubic non-uniform B-spline interpolation algorithm is applied to smooth the generated path. Finally, simulation experiments of the IRRT*-Connect algorithm are conducted in Python and ROS, and physical experiments are performed on a UR5 robotic arm. By comparing with the existing algorithms, it is demonstrated that the proposed method can achieve shorter planning times and lower path costs of the manipulator operation.

Spatio-Temporal Joint Trajectory Planning for Autonomous Vehicles Based on Improved Constrained Iterative LQR

With advancements in autonomous driving technology, the coupling of spatial paths and temporal speeds in complex scenarios becomes increasingly significant. Traditional sequential decoupling methods for trajectory planning are no longer sufficient, emphasizing the need for spatio-temporal joint trajectory planning. The Constrained Iterative LQR (CILQR), based on the Iterative LQR (ILQR) method, shows obvious potential but faces challenges in computational efficiency and scenario adaptability. This paper introduces three key improvements: a segmented barrier function truncation strategy with dynamic relaxation factors to enhance stability, an adaptive weight parameter adjustment method for acceleration and curvature planning, and the integration of the hybrid A* algorithm to optimize the initial reference trajectory and improve iterative efficiency. The improved CILQR method is validated through simulations and real-vehicle tests, demonstrating substantial improvements in human-like driving performance, traffic efficiency improvement, and real-time performance while maintaining comfortable driving. The experiment's results demonstrate a significant increase in human-like driving indicators by 16.35% and a 12.65% average increase in traffic efficiency, reducing computation time by 39.29%.

A Survey of Autonomous Vehicle Behaviors: Trajectory Planning Algorithms, Sensed Collision Risks, and User Expectations

Autonomous vehicles are rapidly advancing and have the potential to revolutionize transportation in the future. This paper primarily focuses on vehicle motion trajectory planning algorithms, examining the methods for estimating collision risks based on sensed environmental information and approaches for achieving user-aligned trajectory planning results. It investigates the different categories of planning algorithms within the scope of local trajectory planning applications for autonomous driving, discussing and differentiating their properties in detail through a review of the recent studies. The risk estimation methods are classified and introduced based on their descriptions of the sensed collision risks in traffic environments and their integration with trajectory planning algorithms. Additionally, various user experience-oriented methods, which utilize human data to enhance the trajectory planning performance and generate human-like trajectories, are explored. The paper provides comparative analyses of these algorithms and methods from different perspectives, revealing the interconnections between these topics. The current challenges and future prospects of the trajectory planning tasks in autonomous vehicles are also discussed.

Path to autonomous soil sampling and analysis by ground-based robots

Good site characterization is essential for the selection of remediation alternatives for impacted soils. The value of site characterization is critically dependent on the quality and quantity of the data collected. Current methods for characterizing impacted soils rely on expensive manual sample collection and off-site analysis. However, recent advances in terrestrial robotics and artificial intelligence offer a potentially revolutionary set of tools and methods that will help to autonomously explore natural environments, select sample locations with the highest value of information, extract samples, and analyze the data in real-time without exposing humans to potentially hazardous conditions. A fundamental challenge to realizing this potential is determining how to design an autonomous system for a given investigation with many, and often conflicting design criteria. This work presents a novel design methodology to navigate these criteria. Specifically, this methodology breaks the system into four components - sensing, sampling, mobility, and autonomy - and connects design variables to the investigation objectives and constraints. These connections are established for each component through a survey of existing technology, discussion of key technical challenges, and highlighting conditions where generality can promote multi-application deployment. An illustrative example of this design process is presented for the development and deployment of a robotic platform characterizing salt-impacted oil & gas reserve pits. After calibration, the relationship between the in situ robot chloride measurements and laboratory-based chloride measurements had a good linear relationship (R2-value = 0.861) and statistical significance (p-value = 0.003).

Optimal Task and Motion Planning and Execution for Multiagent Systems in Dynamic Environments

Combining symbolic and geometric reasoning in multiagent systems is a challenging task that involves planning, scheduling, and synchronization problems. Existing works overlooked the variability of task duration and geometric feasibility intrinsic to these systems because of the interaction between agents and the environment. We propose a combined task and motion planning approach to optimize the sequencing, assignment, and execution of tasks under temporal and spatial variability. The framework relies on decoupling tasks and actions, where an action is one possible geometric realization of a symbolic task. At the task level, timeline-based planning deals with temporal constraints, duration variability, and synergic assignment of tasks. At the action level, online motion planning plans for the actual movements dealing with environmental changes. We demonstrate the approach's effectiveness in a collaborative manufacturing scenario, in which a robotic arm and a human worker shall assemble a mosaic in the shortest time possible. Compared with existing works, our approach applies to a broader range of applications and reduces the execution time of the process.

Position Checking-Based Sampling Approach Combined with Attraction Point Local Optimization for Safe Flight of UAVs

Trading off the allocation of limited computational resources between front-end path generation and back-end trajectory optimization plays a key role in improving the efficiency of unmanned aerial vehicle (UAV) motion planning. In this paper, a sampling-based kinodynamic planning method that can reduce the computational cost as well as the risks of UAV flight is proposed. Firstly, an initial trajectory connecting the start and end points without considering obstacles is generated. Then, a spherical space is constructed around the topological vertices of the environment, based on the intersections of the trajectory with the obstacles. Next, some unnecessary sampling points, as well as node rewiring, are discarded by the designed position-checking strategy to minimize the computational cost and reduce the risks of UAV flight. Finally, in order to make the planning framework adaptable to complex scenarios, the strategies for selecting different attraction points according to the environment are designed, which further ensures the safe flight of the UAV while improving the success rate of the front-end trajectory. Simulations and real-world experiment comparisons are conducted on a vision-based platform to verify the performance of the proposed method.

NA-OR: A path optimization method for manipulators via node attraction and obstacle repulsion

This paper is concerned with the issue of path optimization for manipulators in multi-obstacle environments. Aimed at overcoming the deficiencies of the sampling-based path planning algorithm with high path curvature and low safety margin, a path optimization method, named NA-OR, is proposed for manipulators, where the NA (node attraction) and OR (obstacle repulsion) functions are developed to refine the path by iterations. In the iterations of path optimization, the node attraction function is designed to pull the path nodes toward the center of their neighbor nodes, thereby reducing the path curvature and improving the smoothness. Also, the obstacle repulsion function is developed to push the path nodes out of the potentially unsafe region by generating a repulsive torque on the path nodes, thus improving the safety margin of the motion. By introducing the effect of NA-OR, the optimized path has a significant improvement in path curvature and safety margin compared with the initial path planned by Bi-RRT, which meaningfully enhances the operation ability of manipulators for the applications that give a strong emphasis on security. Experimental results on a 6-DOF manipulator in 4 scenarios demonstrate the effectiveness and superiority of the proposed method in terms of the path cost, safety margin, and path smoothness.

Computationally efficient and sub-optimal trajectory planning framework based on trajectory-quality growth rate analysis

A planetary exploration rover has been used for scientific missions or as a precursor for a future manned mission. The rover’s autonomous system is managed by a space-qualified, radiation-hardened onboard computer; hence, the processing performance for such a computer is strictly limited, owing to the limitation to power supply. Generally, a computationally efficient algorithm in the autonomous system is favorable. This study, therefore, presents a computationally efficient and sub-optimal trajectory planning framework for the rover. The framework exploits an incremental search algorithm, which can generate more optimal solutions as the number of iterations increases. Such an incremental search is subjected to the trade-off between trajectory optimality and computational burden. Therefore, we introduce the trajectory-quality growth rate (TQGR) to statistically analyze the relationship between trajectory optimality and computational cost. This analysis is conducted in several types of terrain, and the planning stop criterion is estimated. Furthermore, the relation between terrain features and the stop criterion is modeled offline by a machine learning technique. Then, using the criterion predicted by the model, the proposed framework appropriately interrupts the incremental search in online motion planning, resulting in a sub-optimal trajectory with less computational burden. Trajectory planning simulation in various real terrain data validates that the proposed framework can, on average, reduce the computational cost by 47.6% while maintaining 63.8% of trajectory optimality. Furthermore, the simulation result shows the proposed framework still performs well even though the planning stop criterion is not adequately predicted.

A Global Path Planning Method for Unmanned Ground Vehicles in Off-Road Environments Based on Mobility Prediction

In a complex off-road environment, due to the low bearing capacity of the soil and the uneven features of the terrain, generating a safe and effective global route for unmanned ground vehicles (UGVs) is critical for the success of their motion and mission. Most traditional global path planning methods simply take the shortest path length as the optimization objective, which makes it difficult to plan a feasible and safe route in complex off-road environments. To address this problem, this research proposes a global path planning method, which considers the influence of terrain factors and soil mechanics on UGV mobility. First, we established a high-resolution 3D terrain model with remote sensing elevation terrain data, land use and soil type distribution data, based on a geostatistical method. Second, we analyzed the vehicle mobility by the terramechanical method (i.e., vehicle cone index and Bakker’s theory), and then calculated the mobility cost based on a fuzzy inference method. Finally, based on the calculated mobility cost, the probabilistic roadmap method was used to establish the connected matrix and the multi-dimensional traffic cost evaluation matrix among the sampling nodes, and then an improved A* algorithm was proposed to generate the global route.

Adaptively Informed Trees (AIT*) and Effort Informed Trees (EIT*): Asymmetric bidirectional sampling-based path planning

Optimal path planning is the problem of finding a valid sequence of states between a start and goal that optimizes an objective. Informed path planning algorithms order their search with problem-specific knowledge expressed as heuristics and can be orders of magnitude more efficient than uninformed algorithms. Heuristics are most effective when they are both accurate and computationally inexpensive to evaluate, but these are often conflicting characteristics. This makes the selection of appropriate heuristics difficult for many problems. This paper presents two almost-surely asymptotically optimal sampling-based path planning algorithms to address this challenge, Adaptively Informed Trees (AIT*) and Effort Informed Trees (EIT*). These algorithms use an asymmetric bidirectional search in which both searches continuously inform each other. This allows AIT* and EIT* to improve planning performance by simultaneously calculating and exploiting increasingly accurate, problem-specific heuristics. The benefits of AIT* and EIT* relative to other sampling-based algorithms are demonstrated on 12 problems in abstract, robotic, and biomedical domains optimizing path length and obstacle clearance. The experiments show that AIT* and EIT* outperform other algorithms on problems optimizing obstacle clearance, where a priori cost heuristics are often ineffective, and still perform well on problems minimizing path length, where such heuristics are often effective.

FC-RRT*: An Improved Path Planning Algorithm for UAV in 3D Complex Environment

In complex environments, path planning is the key for unmanned aerial vehicles (UAVs) to perform military missions autonomously. This paper proposes a novel algorithm called flight cost-based Rapidly-exploring Random Tree star (FC-RRT*) extending the standard Rapidly-exploring Random Tree star (RRT*) to deal with the safety requirements and flight constraints of UAVs in a complex 3D environment. First, a flight cost function that includes threat strength and path length was designed to comprehensively evaluate the connection between two path nodes. Second, in order to solve the UAV path planning problem from the front-end, the flight cost function and flight constraints were used to inspire the expansion of new nodes. Third, the designed cost function was used to guide the update of the parent node to allow the algorithm to consider both the threat and the length of the path when generating the path. The simulation and comparison results show that FC-RRT* effectively overcomes the shortcomings of standard RRT*. FC-RRT* is able to plan an optimal path that significantly improves path safety as well as maintains has the shortest distance while satisfying flight constraints in the complex environment. This paper has application value in UAV 3D global path planning.

Bounded Cost Path Planning for Underwater Vehicles Assisted by a Time-Invariant Partitioned Flow Field Model

A bounded cost path planning method is developed for underwater vehicles assisted by a data-driven flow modeling method. The modeled flow field is partitioned as a set of cells of piece-wise constant flow speed. A flow partition algorithm and a parameter estimation algorithm are proposed to learn the flow field structure and parameters with justified convergence. A bounded cost path planning algorithm is developed taking advantage of the partitioned flow model. An extended potential search method is proposed to determine the sequence of partitions that the optimal path crosses. The optimal path within each partition is then determined by solving a constrained optimization problem. Theoretical justification is provided for the proposed extended potential search method generating the optimal solution. The path planned has the highest probability to satisfy the bounded cost constraint. The performance of the algorithms is demonstrated with experimental and simulation results, which show that the proposed method is more computationally efficient than some of the existing methods.

Batch Informed Trees (BIT*): Informed asymptotically optimal anytime search

Path planning in robotics often requires finding high-quality solutions to continuously valued and/or high-dimensional problems. These problems are challenging and most planning algorithms instead solve simplified approximations. Popular approximations include graphs and random samples, as used by informed graph-based searches and anytime sampling-based planners, respectively.

Informed graph-based searches, such as A*, traditionally use heuristics to search a priori graphs in order of potential solution quality. This makes their search efficient, but leaves their performance dependent on the chosen approximation. If the resolution of the chosen approximation is too low, then they may not find a (suitable) solution, but if it is too high, then they may take a prohibitively long time to do so.

Anytime sampling-based planners, such as RRT*, traditionally use random sampling to approximate the problem domain incrementally. This allows them to increase resolution until a suitable solution is found, but makes their search dependent on the order of approximation. Arbitrary sequences of random samples approximate the problem domain in every direction simultaneously, but may be prohibitively inefficient at containing a solution.

This article unifies and extends these two approaches to develop Batch Informed Trees (BIT*), an informed, anytime sampling-based planner. BIT* solves continuous path planning problems efficiently by using sampling and heuristics to alternately approximate and search the problem domain. Its search is ordered by potential solution quality, as in A*, and its approximation improves indefinitely with additional computational time, as in RRT*. It is shown analytically to be almost-surely asymptotically optimal and experimentally to outperform existing sampling-based planners, especially on high-dimensional planning problems.

Optimizing Motion-Planning Problem Setup via Bounded Evaluation with Application to Following Surgical Trajectories

A motion-planning problem's setup can drastically affect the quality of solutions returned by the planner. In this work we consider optimizing these setups, with a focus on doing so in a computationally-efficient fashion. Our approach interleaves optimization with motion planning, which allows us to consider the actual motions required of the robot. Similar prior work has treated the planner as a black box: our key insight is that opening this box in a simple-yet-effective manner enables a more efficient approach, by allowing us to bound the work done by the planner to optimizer-relevant computations. Finally, we apply our approach to a surgically-relevant motion-planning task, where our experiments validate our approach by more-efficiently optimizing the fixed insertion pose of a surgical robot.

Confidence random tree-based algorithm for mobile robot path planning considering the path length and safety

This article introduces a novel confidence random tree-based sampling path planning algorithm for mobile service robots operating in real environments. The algorithm is time efficient, can accommodate narrow corridors, enumerates possible solutions, and minimizes the cost of the path. These benefits are realized by incorporating notable approaches from other existing path planning algorithms into the proposed algorithm. During path selection, the algorithm considers the length and safety of each path via a sampling and rejection method. The algorithm operates as follows. First, the confidence of a path is computed based on the clearance required to ensure the safety of the robot, where the clearance is defined as the distance between the path and the closest obstacle. Then, the sampling method generates a tree graph in which the edge lengths are controlled by the confidence. In a low confidence space, such as a narrow corridor, the corresponding graph has denser samples with short edges while in a high confidence space, the samples are widely spaced with longer edges. Finally, a rejection method is employed to ensure a reasonably short computation time by optimizing the sample density by rejecting unnecessary samples. The performance of the proposed algorithm is validated by comparing the experimental results to those of several commonly used algorithms.