Systematic Literature Review of Sampling Process in Rapidly-Exploring Random Trees
---
paper_title: Sampling-Based Real-Time Motion Planning under State Uncertainty for Autonomous Micro-Aerial Vehicles in GPS-Denied Environments

paper_content:

This paper presents a real-time motion planning approach for autonomous vehicles with complex dynamics and state uncertainty. The approach is motivated by the motion planning problem for autonomous vehicles navigating in GPS-denied dynamic environments, which involves non-linear and/or non-holonomic vehicle dynamics, incomplete state estimates, and constraints imposed by uncertain and cluttered environments. To address the above motion planning problem, we propose an extension of the closed-loop rapid belief trees, the closed-loop random belief trees (CL-RBT), which incorporates predictions of the position estimation uncertainty, using a factored form of the covariance provided by the Kalman filter-based estimator. The proposed motion planner operates by incrementally constructing a tree of dynamically feasible trajectories using the closed-loop prediction, while selecting candidate paths with low uncertainty using efficient covariance update and propagation. The algorithm can operate in real-time, continuously providing the controller with feasible paths for execution, enabling the vehicle to account for dynamic and uncertain environments. Simulation results demonstrate that the proposed approach can generate feasible trajectories that reduce the state estimation uncertainty, while handling complex vehicle dynamics and environment constraints.
---
paper_title: Application of artificial fish school algorithm in UCAV path planning

paper_content:

The path planning method based on artificial fish school algorithm (AFSA) was proposed to solve unmanned combat aerial vehicle (UCAV) path planning problem under the 2-D radar threats environment. According to the path planning requirements, the threat detection and artificial fish coding method were designed in detail. Besides, the method of perceiving threats was applied for advancing the feasibility of the path. A comparison of the results was made by WPSO, CFPSO and AFSA, which showed that the method we proposed in this paper was effective. AFSA was much more suitable for solving this kind of problem.
---
paper_title: Tunnel detection in protein structures using sampling-based motion planning

paper_content:

Proteins are involved in many biochemical processes. The behavior of proteins is influenced by internal void space such as tunnels or cavities. Tunnels are paths leading from an inner protein active site to its surface. The knowledge about tunnels and their evolution over time provides an insight into protein properties (e.g., stability). Sampling-based motion planning techniques like Rapidly Exploring Random Tree (RRT) can be used to find tunnels by sampling the corresponding configuration space. These methods can be easily adapted to operate with protein dynamics. The inner void space of proteins is very limited, which may decrease the ability of RRT to find a solution due to the narrow passage problem. In this paper, we propose to generate random samples using a Voronoi Diagram of the atoms. A subset of Voronoi vertices is dynamically maintained to support the generation of samples in promising regions inside the protein.
---
paper_title: Physics-based virtual reality for task learning and intelligent disassembly planning

paper_content:

Physics-based simulation is increasingly important in virtual manufacturing for product assembly and disassembly operations. This work explores potential benefits of physics-based modeling for automatic learning of assembly tasks and for intelligent disassembly planning in desktop virtual reality. The paper shows how realistic physical animation of manipulation tasks can be exploited for learning sequential constraints from user demonstrations. In particular, a method is proposed where information about physical interaction is used to discover task precedences and to reason about task similarities. A second contribution of the paper is the application of physics-based modeling to the problem of disassembly sequence planning. A novel approach is described to find all physically admissible subassemblies in which a set of rigid objects can be disassembled. Moreover, efficient strategies are presented aimed at reducing the computational time required for automatic disassembly planning. The proposed strategies take into account precedence relations arising from user assembly demonstrations as well as geometrical clustering. A motion planning technique has also been developed to generate non-destructive disassembly paths in a query-based approach. Experiments have been performed in an interactive virtual environment including a dataglove and motion tracker that allows realistic object manipulation and grasping.
---
paper_title: Model-Driven Engineering for Mobile Robot Systems: A systematic mapping study

paper_content:

The development of autonomous Mobile Robot Systems is attracting nowadays more and moreinterest from both researchers and practitioners, mainly because they may open for a wide rangeof improvements for quality of life. Mobile robots are systems capable of accomplishing missionsby moving in an unknown environment without human supervision. Throughout mechanisms ofdetection, communication and adaptation, they can adapt their behavior according to changes ofthe environment. Individual robots can even join teams of autonomous mobile robots that, throughindividual tasks, accomplish common missions. These are called Mobile Multi-Robot Systems andare meant to perform missions that a single robot would not be able to carry out by itself.When it comes to the development of Mobile Robot Systems, currently there is no standard methodology.This is mainly due to the complexity of the domain and the variety of di↵erent platformsthat are available on the market. A promising methodology that recently has gained attention insoftware industry for its ability of mitigating complexity and boosting platform-independence, isModel-Driven Engineering.This thesis proposes a systematic mapping study on the state-of-the-art of Model-Driven Engineeringfor Mobile Robot Systems. Through our contribution, researchers can get a picture of theactual trends and open challenges for further research, while practitioners can realize the suitabilityof Model-Driven Engineering by checking to what extent it has been applied to real-world projects.
---
paper_title: Incremental Sampling-based Algorithms for Optimal Motion Planning

paper_content:

During the last decade, incremental sampling-based motion planning algorithms, such as the Rapidly-exploring Random Trees (RRTs), have been shown to work well in practice and to possess theoretical guarantees such as probabilistic completeness. However, no theoretical bounds on the quality of the solution obtained by these algorithms, e.g., in terms of a given cost function, have been established so far. The purpose of this paper is to fill this gap, by designing efficient incremental samplingbased algorithms with provable optimality properties. The first contribution of this paper is a negative result: it is proven that, under mild technical conditions, the cost of the best path returned by RRT converges almost surely to a non-optimal value, as the number of samples increases. Second, a new algorithm is considered, called the Rapidly-exploring Random Graph (RRG), and it is shown that the cost of the best path returned by RRG converges to the optimum almost surely. Third, a tree version of RRG is introduced, called RRT∗, which preserves the asymptotic optimality of RRG while maintaining a tree structure like RRT. The analysis of the new algorithms hinges on novel connections between sampling-based motion planning algorithms and the theory of random geometric graphs. In terms of computational complexity, it is shown that the number of simple operations required by both the RRG and RRT∗ algorithms is asymptotically within a constant factor of that required by RRT.
---
paper_title: Optimal Path Planning using RRT* based Approaches: A Survey and Future Directions

paper_content:

Optimal path planning refers to find the collision free, shortest, and smooth route between start and goal positions. This task is essential in many robotic applications such as autonomous car, surveillance operations, agricultural robots, planetary and space exploration missions. Rapidly-exploring Random Tree Star (RRT*) is a renowned sampling based planning approach. It has gained immense popularity due to its support for high dimensional complex problems. A significant body of research has addressed the problem of optimal path planning for mobile robots using RRT* based approaches. However, no updated survey on RRT* based approaches is available. Considering the rapid pace of development in this field, this paper presents a comprehensive review of RRT* based path planning approaches. Current issues relevant to noticeable advancements in the field are investigated and whole discussion is concluded with challenges and future research directions.
---
paper_title: Sampling-Based Robot Motion Planning: A Review

paper_content:

Motion planning is a fundamental research area in robotics. Sampling-based methods offer an efficient solution for what is otherwise a rather challenging dilemma of path planning. Consequently, these methods have been extended further away from basic robot planning into further difficult scenarios and diverse applications. A comprehensive survey of the growing body of work in sampling-based planning is given here. Simulations are executed to evaluate some of the proposed planners and highlight some of the implementation details that are often left unspecified. An emphasis is placed on contemporary research directions in this field. We address planners that tackle current issues in robotics. For instance, real-life kinodynamic planning, optimal planning, replanning in dynamic environments, and planning under uncertainty are discussed. The aim of this paper is to survey the state of the art in motion planning and to assess selected planners, examine implementation details and above all shed a light on the current challenges in motion planning and the promising approaches that will potentially overcome those problems.
---
paper_title: Time-optimal path planning in dynamic flows using level set equations: theory and schemes

paper_content:

We develop an accurate partial differential equation-based methodology that predicts the time-optimal paths of autonomous vehicles navigating in any continuous, strong, and dynamic ocean currents, obviating the need for heuristics. The goal is to predict a sequence of steering directions so that vehicles can best utilize or avoid currents to minimize their travel time. Inspired by the level set method, we derive and demonstrate that a modified level set equation governs the time-optimal path in any continuous flow. We show that our algorithm is computationally efficient and apply it to a number of experiments. First, we validate our approach through a simple benchmark application in a Rankine vortex flow for which an analytical solution is available. Next, we apply our methodology to more complex, simulated flow fields such as unsteady double-gyre flows driven by wind stress and flows behind a circular island. These examples show that time-optimal paths for multiple vehicles can be planned even in the presence of complex flows in domains with obstacles. Finally, we present and support through illustrations several remarks that describe specific features of our methodology.
---
paper_title: Steps toward derandomizing RRTs

paper_content:

We present two new motion planning algorithms, based on the rapidly exploring random tree (RRT) family of algorithms. These algorithms represent the first work in the direction of derandomizing RRTs; this is a very challenging problem due to the way randomization is used in RRTs. In RRTs, randomization is used to create Voronoi bias, which causes the search trees to rapidly explore the state space. Our algorithms take steps to increase the Voronoi bias and to retain this property without the use of randomization. Studying these and related algorithms would improve our understanding of how efficient exploration can be accomplished, and would hopefully lead to improved planners. We give experimental results that illustrate how the new algorithms explore the state space and how they compare with existing RRT algorithms.
---
paper_title: Trajectory planning with look-ahead for Unmanned Sea Surface Vehicles to handle environmental disturbances

paper_content:

We present a look-ahead based trajectory planning algorithm for computation of dynamically feasible trajectories for Unmanned Sea Surface Vehicles (USSV) operating in high seas states. The algorithm combines A* based heuristic search and locally bounded optimal planning under motion uncertainty using a variation of the minimax game-tree search. This allows the algorithm to compute trajectories that explicitly consider the possibility of the vehicle safely deviating from its original course due to the ocean waves within a specified look-ahead region. The algorithm can adapt its search based on the user-specified risk thresholds. Moreover, the algorithm produces a contingency plan as a part of the computed trajectory. We demonstrate the capabilities of the algorithm using simulations.
---
paper_title: Randomized kinodynamic planning

paper_content:

The paper presents a state-space perspective on the kinodynamic planning problem, and introduces a randomized path planning technique that computes collision-free kinodynamic trajectories for high degree-of-freedom problems. By using a state space formulation, the kinodynamic planning problem is treated as a 2n-dimensional nonholonomic planning problem, derived from an n-dimensional configuration space. The state space serves the same role as the configuration space for basic path planning. The bases for the approach is the construction of a tree that attempts to rapidly and uniformly explore the state space, offering benefits that are similar to those obtained by successful randomized planning methods, but applies to a much broader class of problems. Some preliminary results are discussed for an implementation that determines the kinodynamic trajectories for hovercrafts and satellites in cluttered environments resulting in state spaces of up to twelve dimensions.
---
paper_title: An autonomous blimp for a surveillance system

paper_content:

An autonomous blimp for a surveillance system, which is circling around a specified target with only one camera, is designed in this paper. For this purpose, an extension of Lucas-Kanade algorithm for detection and tracking of features with rotation and scaling is provided, and a simplified structure-from-motion algorithm is applied to improve the accuracy of state estimation. A tracking controller is designed for the blimp which is an underactuated system. The desired path of the blimp is also generated from image information of a target. The blimp flies around the target automatically, after a commander sets it. Some experiments are performed indoors by using an aerial blimp.
---
paper_title: Goal-oriented stimulus generation for analog circuits

paper_content:

We present a methodology to generate goal-oriented test cases for verifying nonlinear analog circuits. We use a learning-based approach to identify the goal regions in circuit's state space. We use the information that we learn to guide the growth of Rapidly-exploring Random Trees (RRTs) towards these goal regions. Compared to previous approaches for test generation, our methodology generates several test cases of the circuit that are more concentrated in the relevant operating regions. We demonstrate the effectiveness of our approach on typical case studies. We show that our methodology can be used to generate test cases for undesirable behavior that was previously hard to detect.
---
paper_title: 3D-shortest paths for a hypersonic glider in a heterogeneous environment

paper_content:

Abstract Shortest paths in 3-dimensional space of a hypersonic glider in a heterogeneous environment are considered in this paper. The environment is heterogeneous in the sense that the maximum curvature of the vehicle path varies and depends on the position of the vehicle. Path generation is based on the Dubins-like model. It assumes that initial and final states are sufficiently far from each other so that the CSC (Curve-Straight line-Curve) path is the shortest path between both states. Paths are calculated based on the optimal control theory and a geometrical approach. This method is computationally fast and easy to implement in a real time system. Moreover, paths found by this method are more realistic than existing Dubins’ paths.
---
paper_title: Parallel RRT∗ architecture design for motion planning

paper_content:

A motion planning algorithm aims to calculate one obstacle-free trajectory which meets the dynamical constraints of a vehicle and leads the vehicle from the start state to the target state. RRT∗ (RRT star) is one sampling-based algorithm which is widely used in many applications because of its speed in quickly finding a trajectory. In contrast with basic RRT (Rapidly-exploring Random Trees) algorithm, RRT∗ improves trajectory optimality significantly by introducing the refinement step after setting up each tree node. This paper describes a new parallel version of the RRT∗ algorithm and its corresponding architecture on an FPGA (Field Programmable Gate Arrays). The refinement step is extracted and runs as a parallel process alongside a continuous tree-extending process. In order to avoid traversing all nodes in every iteration, tree nodes are stored in separate memory blocks and each block is assigned its own tree extending and refining pipelines to enhance the memory throughput. In the experimental evaluation, we take a 3-dimensional state spaces and implement the proposed architecture. The hardware implementation gives a 90 times speed improvement compared with an embedded software implementation, and a 30 times speedup compared to a desktop software implementation.
---
paper_title: RRT-Based Game Level Analysis, Visualization, and Visual Refinement

paper_content:

Automating parts of game creation benefits both professional and amateur game designers and much previous work has already made progress on this front. In this paper we tackle automating level design. We describe a general graph-based representation for game levels and present a preliminary system that leverages this representation. Our system automatically explores existing levels of a 2D platform game using the rapidly-exploring random tree (RRT) algorithm and constructs a compact graph representation from this exploration. Our system can also modify a graph representation on-the-fly to reflect user-directed changes to the existing level structure. This work constitutes an initial step toward the larger goal of automating level design in a general way.
---
paper_title: Online dead-lock avoidance scheme of wheeled mobile robot under the presence of boxlike obstacles

paper_content:

This paper presents a path planner for the design of autonomous vehicles such as mobile robots. The path planner is based on the potential field method. Through the Hough transformation the obstacle detection is accomplished by laser scanner which returns a two dimensional profile of the horizontal region in front of the robot. The local minima problem has been solved by redefining the repulsive potential field. Also the system controller (look-ahead control) gives the robot the capability of controlling the distance between the reference point and the center of the robot. As a result, the potential field method performs effectively under our system and allows the mobile robot to follow a smooth trajectory in a flexible manner for attaining the desired goal autonomously whether in a static or dynamic environment
---
paper_title: Randomized path planning for redundant manipulators without inverse kinematics

paper_content:

We present a sampling-based path planning algorithm capable of efficiently generating solutions for high-dimensional manipulation problems involving challenging inverse kinematics and complex obstacles. Our algorithm extends the rapidly-exploring random tree (RRT) algorithm to cope with goals that are specified in a subspace of the manipulator configuration space through which the search tree is being grown. Underspecified goals occur naturally in arm planning, where the final end effector position is crucial but the configuration of the rest of the arm is not. To achieve this, the algorithm bootstraps an optimal local controller based on the transpose of the Jacobian to a global RRT search. The resulting approach, known as Jacobian transpose-directed rapidly exploring random trees (JT-RRTs), is able to combine the configuration space exploration of RRTs with a workspace goal bias to produce direct paths through complex environments extremely efficiently, without the need for any inverse kinematics. We compare our algorithm to a recently-developed competing approach and provide results from both simulation and a 7 degree-of-freedom robotic arm.
---
paper_title: Artificial Intelligence for Computer Games: An Introduction

paper_content:

Learn to make games that are more fun and engaging! Building on fundamental principles of Artificial Intelligence, Funge explains how to create Non-Player Characters (NPCs) with progressively more sophisticated capabilities. Starting with the basic capability of acting in the game world, the book explains how to develop NPCs who can perceive, remember what they perceive, and then continue in the game play to think about the effects of possible actions, and finally learn from their experience. Funge considers the system architecture and explains how to implement potential behaviors (both reactive and deliberate) for intelligent and responsive NPCs allowing for games that are more fun and engaging. Emphasizing enduring design principles, Funge covers the basics of Game AI and provides a clear, easy to read introduction that beginning programmers and game designers will enjoy.
---
paper_title: Singularity robust path planning for real time base attitude adjustment of free-floating space robot

paper_content:

This paper presents a singularity robust path planning for space manipulator to achieve base (satellite) attitude adjustment and end-effector task. The base attitude adjustment by the movement of manipulator will save propellant compared with conventional attitude control system. A task-priority reaction null-space control method is applied to achieve the primary task of adjusting attitude and secondary task of accomplishing end-effector task. Furthermore, the algorithm singularity is eliminated in the proposed algorithm compared with conventional reaction null-space algorithm. And the singular value filtering decomposition is introduced to dispose the dynamic singularity, the unit quaternion is also introduced to overcome representation singularity. Hence, a singularity robust path planning algorithm of space robot for base attitude adjustment is derived. A real time simulation system of the space robot under Linux/RTAI (realtime application interface) is developed to verify and test the feasibility and reliability of the method. The experimental results demonstrate the feasibility of online base attitude adjustment of space robot by the proposed algorithm.
---
paper_title: An Improved Anytime RRTs Algorithm

paper_content:

Mobile robots often need to find a trajectory to another position in their environment, subject to constraints posed by obstacles and the robot’s capabilities. Several approaches have been used to address this problem each with some limitations, including state discretizations, planning efficiency, and lack of interleaved execution. Anytime RRTs Algorithm is a recently developed algorithm on which fast continuous domain path planners can be based. This paper presents a modification to the Anytime RRTs Algorithm. Optimization include a more general biased distribution, which was explored in this work in the form of a waypoint cache. Which improve replanning efficiency and the quality of generated paths. We demonstrate the effectiveness of the algorithm on single robot planning domains.
---
paper_title: Performing systematic literature reviews in software engineering

paper_content:

Context: Making best use of the growing number of empirical studies in Software Engineering, for making decisions and formulating research questions, requires the ability to construct an objective summary of available research evidence. Adopting a systematic approach to assessing and aggregating the outcomes from a set of empirical studies is also particularly important in Software Engineering, given that such studies may employ very different experimental forms and be undertaken in very different experimental contexts.Objectives: To provide an introduction to the role, form and processes involved in performing Systematic Literature Reviews. After the tutorial, participants should be able to read and use such reviews, and have gained the knowledge needed to conduct systematic reviews of their own.Method: We will use a blend of information presentation (including some experiences of the problems that can arise in the Software Engineering domain), and also of interactive working, using review material prepared in advance.
---
paper_title: Optimal and Efficient Path Planning for Unknown and Dynamic Environments

paper_content:

Abstract : The task of planning trajectories for a mobile robot has received considerable attention in the research literature. Algorithms exist for handling a variety of robot shapes, configurations, motion constraints, and environments. Most of the work assumes the robot has a complete and accurate model of its environment before it begins to move; less attention has been paid to the problem of unknown or partially-known environments. This situation occurs for an exploratory robot or one that must move to a goal location without the benefit of a floorplan (indoor) or terrain map (outdoor). Existing approaches plan an initial global path or route based on known information and then modify the plan locally as the robot discovers obstacles with its sensors. While this strategy works well in environments with small, sparse obstacles, it can lead to grossly suboptimal and incomplete results in cluttered spaces. An alternative approach is to replan the global path from scratch each time a new obstacle is discovered.
---
paper_title: A Formal Basis for the Heuristic Determination of Minimum Cost Paths

paper_content:

Although the problem of determining the minimum cost path through a graph arises naturally in a number of interesting applications, there has been no underlying theory to guide the development of efficient search procedures. Moreover, there is no adequate conceptual framework within which the various ad hoc search strategies proposed to date can be compared. This paper describes how heuristic information from the problem domain can be incorporated into a formal mathematical theory of graph searching and demonstrates an optimality property of a class of search strategies.
---
paper_title: Cooperative On-Line Planning For Adaptive Map Building In Environmental Applications

paper_content:

Two adaptive on-line planning algorithms for the exploration of an unknown environment by cooperating autonomous underwater vehicles are introduced and compared. The algorithms are suited for a team of autonomous vehicles taking point-wise environmental measurements over an ocean region, with the final objective of producing an estimated map of the measured environmental quantity over the whole region. Simulative test cases in which the algorithm performances are compared with that theoretically achievable by Rapidly-exploring Random Tree search are presented.
---
paper_title: A fuzzy approach to the weighted region problem for autonomous vehicles

paper_content:

An approach is proposed to represent and reason about the uncertainty in terrain description by using fuzzy set theory. The whole terrain is assumed to be classified into a set of fuzzy regions, and weight of region is interpreted as a linguistic variable whose values are linguistic labels of fuzzy sets. Based on this representation, a decision function is established whose minus gradient information is used to lead the vehicle to travel to its goal with an acceptable cost. >
---
paper_title: The Ariadne's Clew Algorithm

paper_content:

We present a new approach to path planning, called the "Ariadne's clew algorithm". It is designed to find paths in high-dimensional continuous spaces and applies to robots with many degrees of freedom in static, as well as dynamic environments -- ones where obstacles may move. The Ariadne's clew algorithm comprises two sub-algorithms, called SEARCH and EXPLORE, applied in an interleaved manner. EXPLORE builds a representation of the accessible space while SEARCH looks for the target. Both are posed as optimization problems. We describe a real implementation of the algorithm to plan paths for a six degrees of freedom arm in a dynamic environment where another six degrees of freedom arm is used as a moving obstacle. Experimental results show that a path is found in about one second without any pre-processing.
---
paper_title: Sampling-based algorithms for optimal motion planning

paper_content:

United States. Air Force Office of Scientific Research (Michigan/AFRL Collaborative Center in Control Science Grant FA 8650-07-2-3744)
---
paper_title: Ant Algorithms for Discrete Optimization

paper_content:

This article presents an overview of recent work on ant algorithms, that is, algorithms for discrete optimization that took inspiration from the observation of ant colonies' foraging behavior, and introduces the ant colony optimization (ACO) metaheuristic. In the first part of the article the basic biological findings on real ants are reviewed and their artificial counterparts as well as the ACO metaheuristic are defined. In the second part of the article a number of applications of ACO algorithms to combinatorial optimization and routing in communications networks are described. We conclude with a discussion of related work and of some of the most important aspects of the ACO metaheuristic.
---
paper_title: Application of artificial fish school algorithm in UCAV path planning

paper_content:

The path planning method based on artificial fish school algorithm (AFSA) was proposed to solve unmanned combat aerial vehicle (UCAV) path planning problem under the 2-D radar threats environment. According to the path planning requirements, the threat detection and artificial fish coding method were designed in detail. Besides, the method of perceiving threats was applied for advancing the feasibility of the path. A comparison of the results was made by WPSO, CFPSO and AFSA, which showed that the method we proposed in this paper was effective. AFSA was much more suitable for solving this kind of problem.
---
paper_title: Lifelong Planning A*

paper_content:

Heuristic search methods promise to find shortest paths for path-planning problems faster than uninformed search methods. Incremental search methods, on the other hand, promise to find shortest paths for series of similar path-planning problems faster than is possible by solving each path-planning problem from scratch. In this article, we develop Lifelong Planning A* (LPA*), an incremental version of A* that combines ideas from the artificial intelligence and the algorithms literature. It repeatedly finds shortest paths from a given start vertex to a given goal vertex while the edge costs of a graph change or vertices are added or deleted. Its first search is the same as that of a version of A* that breaks ties in favor of vertices with smaller g-values but many of the subsequent searches are potentially faster because it reuses those parts of the previous search tree that are identical to the new one. We present analytical results that demonstrate its similarity to A* and experimental results that demonstrate its potential advantage in two different domains if the path-planning problems change only slightly and the changes are close to the goal.
---
paper_title: PATH PLANNING IN EXPANSIVE CONFIGURATION SPACES

paper_content:

We introduce the notion of expansiveness to characterize a family of robot configuration spaces whose connectivity can be effectively captured by a roadmap of randomly-sampled milestones. The analysis of expansive configuration spaces has inspired us to develop a new randomized planning algorithm. This new algorithm tries to sample only the portion of the configuration space that is relevant to the current query, avoiding the cost of precomputing a roadmap for the entire configuration space. Thus, it is well-suited for problems where only a single query is submitted for a given environment. The algorithm has been implemented and successfully applied to complex assembly maintainability problems from the automotive industry.
---
paper_title: Improved ant colony optimization algorithm for UAV path planning

paper_content:

Traditional Unmanned aerial vehicles (UAV) path planning methods have poor practical properties as they rarely take mission constraints like terminal angle constraint into consideration. A bidirectional searching ant colony optimization algorithm was proposed to solve above problem without losing path searching efficiency. The workspace of UAV was modeled by applying grid method and each grid was labeled. Then ant colonies start searching from two positions near the starting point and destination point simultaneously following the predetermined directions. A novel path selecting method was used to combine the paths and choose the optimal ones as the final path when the two paths from different points. Pheromone updating rules and successive points selecting method were also improved to increase algorithm convergence speed and avoid local optima. Simulations were made in two grid maps and the results showed that the modified path planning algorithm could find the qualified paths if the one exists with higher efficiency.
---
paper_title: Sampling-Based Robot Motion Planning: A Review

paper_content:

Motion planning is a fundamental research area in robotics. Sampling-based methods offer an efficient solution for what is otherwise a rather challenging dilemma of path planning. Consequently, these methods have been extended further away from basic robot planning into further difficult scenarios and diverse applications. A comprehensive survey of the growing body of work in sampling-based planning is given here. Simulations are executed to evaluate some of the proposed planners and highlight some of the implementation details that are often left unspecified. An emphasis is placed on contemporary research directions in this field. We address planners that tackle current issues in robotics. For instance, real-life kinodynamic planning, optimal planning, replanning in dynamic environments, and planning under uncertainty are discussed. The aim of this paper is to survey the state of the art in motion planning and to assess selected planners, examine implementation details and above all shed a light on the current challenges in motion planning and the promising approaches that will potentially overcome those problems.
---
paper_title: Anytime search in dynamic graphs

paper_content:

Agents operating in the real world often have limited time available for planning their next actions. Producing optimal plans is infeasible in these scenarios. Instead, agents must be satisfied with the best plans they can generate within the time available. One class of planners well-suited to this task are anytime planners, which quickly find an initial, highly suboptimal plan, and then improve this plan until time runs out. A second challenge associated with planning in the real world is that models are usually imperfect and environments are often dynamic. Thus, agents need to update their models and consequently plans over time. Incremental planners, which make use of the results of previous planning efforts to generate a new plan, can substantially speed up each planning episode in such cases. In this paper, we present an A^*-based anytime search algorithm that produces significantly better solutions than current approaches, while also providing suboptimality bounds on the quality of the solution at any point in time. We also present an extension of this algorithm that is both anytime and incremental. This extension improves its current solution while deliberation time allows and is able to incrementally repair its solution when changes to the world model occur. We provide a number of theoretical and experimental results and demonstrate the effectiveness of the approaches in a robot navigation domain involving two physical systems. We believe that the simplicity, theoretical properties, and generality of the presented methods make them well suited to a range of search problems involving dynamic graphs.
---
paper_title: Pythagorean-Hodograph Curves.

paper_content:

This chapter provides an introduction to pythagorean-hodograph (PH) Curves, which offer many advantages, such as rational offsets, superior shape properties, and real-time interpolators. Apart from these practical advantages, the investigation of PH curves is of considerable intellectual appeal for the wealth of mathematical ideas it entails, including the geometry of complex numbers, inaugurated by Wessel, Argand, and Gauss; Hamilton's quaternions and the geometrical algebras of Clifford; medial axis transforms and the Minkowski metric of special relativity; projective geometry and dual representations; the cyclographic map and Laguerre geometry; and connections with classical geometrical optics. The distinguishing feature of a polynomial PH curve is that the components of its hodograph satisfy a Pythagorean condition—that is, the sum of their squares is equal to the square of a polynomial. By virtue of their special algebraic structure, PH curves provide exact solutions to a number of basic geometrical problems in computer-aided design and manufacturing.
---
paper_title: Local trajectory planning and tracking of autonomous vehicles, using clothoid tentacles method

paper_content:

In general, autonomous navigation requires three key steps, the perception of the environment surrounding the vehicle, the trajectory planning and the actuators control. Numerous works on the localization, perception, generation of occupancy grids and control of vehicles were developed within the ASER team at Heudiasyc laboratory. The work presented in this paper covers, essentially, trajectory planning and is based on the results of these works. The challenge is to avoid static and dynamic obstacles at high speed, using real time algorithms. The planning method developed in this work uses an empirical approach for local path planning. This approach consists on drawing clothoid tentacles in the ego-centered reference frame related to the vehicle. An occupancy grid represents the environment surrounding the vehicle and is considered to be ego-centered around it. Using the information of the occupancy grid, each tentacle is classified as navigable or not navigable. Among the navigable tentacles, only one tentacle is chosen as the vehicle reference trajectory using several criteria. The chosen tentacle is then applied to the vehicle using a lateral controller based on Immersion and Invariance principle (I&I).
---
paper_title: Continuous-Curvature Path Planning With Obstacle Avoidance Using Four Parameter Logistic Curves

paper_content:

Continuous-curvature path planning with obstacle avoidance is considered. Two path shapes, namely, S and half-S shapes derived from four parameter logistic curves are proposed as solution paths. Closed-form analytic conditions are derived for avoiding rectangular and circular obstacles. Using the zero end curvature property of the proposed paths, a complete path planner is presented joining the individual paths. An analytic bound on the maximum curvature of the paths is derived. A comparison is carried out with existing smooth path planning methodologies based on number of design parameters, complexity in obstacle avoidance, and nature of computations involved. The work highlights the use of logistic curves as a novel, analytically feasible, and applicable path planning methodology.
---
paper_title: Visible Decomposition: Real-Time Path Planning in Large Planar Environments

paper_content:

We describe a method called Visible Decomposition for computing collision- free paths in real time through a planar environment with a large number of obstacles. This method divides space into local visibility graphs, ensuring that all operations are local. The search time is kept low since the number of regions is proved to be small. We analyze the computational demands of the algorithm and the quality of the paths it produces. In addition, we show test results on a large simulation testbed.
---
paper_title: Safe path planning among multi obstacles

paper_content:

This paper proposed a practical path-planning algorithm for an autonomous vehicle or a car-like robot in an unknown semi-structured (or unstructured) environment, where obstacles are detected online by the vehicle's sensors. The algorithm is based on particle filter, Bezier curves and support vector machine to provide a safe path among various static and moving obstacles and to satisfy the vehicle's curvature constraints. The algorithm has been implemented and verified on the simulation software. Experimental results demonstrate the effectiveness of the proposed method in complicated conditions with existing of multi objects.
---
paper_title: Fast marching tree: A fast marching sampling-based method for optimal motion planning in many dimensions

paper_content:

In this paper we present a novel probabilistic sampling-based motion planning algorithm called the Fast Marching Tree algorithm (FMT*). The algorithm is specifically aimed at solving complex motion planning problems in high-dimensional configuration spaces. This algorithm is proven to be asymptotically optimal and is shown to converge to an optimal solution faster than its state-of-the-art counterparts, chiefly PRM* and RRT*. The FMT* algorithm performs a "lazy" dynamic programming recursion on a predetermined number of probabilistically-drawn samples to grow a tree of paths, which moves steadily outward in cost-to-arrive space. As such, this algorithm combines features of both single-query algorithms (chiefly RRT) and multiple-query algorithms (chiefly PRM), and is reminiscent of the Fast Marching Method for the solution of Eikonal equations. As a departure from previous analysis approaches that are based on the notion of almost sure convergence, the FMT* algorithm is analyzed under the notion of convergence in probability: the extra mathematical flexibility of this approach allows for convergence rate bounds-the first in the field of optimal sampling-based motion planning. Specifically, for a certain selection of tuning parameters and configuration spaces, we obtain a convergence rate bound of order O(n-1/d+ρ), where n is the number of sampled points, d is the dimension of the configuration space, and ρ is an arbitrarily small constant. We go on to demonstrate asymptotic optimality for a number of variations on FMT*, namely when the configuration space is sampled non-uniformly, when the cost is not arc length, and when connections are made based on the number of nearest neighbors instead of a fixed connection radius. Numerical experiments over a range of dimensions and obstacle configurations confirm our the-oretical and heuristic arguments by showing that FMT*, for a given execution time, returns substantially better solutions than either PRM* or RRT*, especially in high-dimensional configuration spaces and in scenarios where collision-checking is expensive.
---
paper_title: Curvature continuous path generation for autonomous vehicle using B-spline curves

paper_content:

In this paper we introduce a roadmap algorithm for generating collision-free paths in terms of cubic B-spline curves for unmanned vehicles used in mining operations. The algorithm automatically generates collision-free paths that are curvature continuous with an upper bounded curvature and a small slope discontinuity of curvature at knots, when we are given the locations of the obstacles, the boundary geometry of the working area, positions and directions of the vehicle at the start, loading, and the goal points. Our algorithm also allows us to find a switch back point where the vehicle reverses its direction to enter the loading area. Examples are provided to demonstrate the effectiveness of the proposed algorithms.
---
paper_title: Path planning with Pythagorean-hodograph curves for unmanned or autonomous vehicles

paper_content:

Pythagorean-hodograph (PH) curves offer distinct advantages in planning curvilinear paths for unmanned or autonomous air, ground, or underwater vehicles. Although several authors have discussed their use in these contexts, prior studies contain misconceptions about the properties of PH curves or invoke heuristic approximate constructions when exact methods are available. To address these issues, the present study provides a basic introduction to the key properties of PH curves, and describes some exact constructions of particular interest in path planning. These include (a) maintenance of minimum safe separations within vehicle swarms; (b) construction of paths of different shape but identical arc length, ensuring simultaneous arrival of vehicles travelling at a constant speed; (c) determination of the curvature extrema of PH paths, and their modification to satisfy a given curvature bound; and (d) construction of curvature-continuous paths of bounded curvature through fields of polygonal obstacles.
---
paper_title: A neural network approach to complete coverage path planning

paper_content:

Complete coverage path planning requires the robot path to cover every part of the workspace, which is an essential issue in cleaning robots and many other robotic applications such as vacuum robots, painter robots, land mine detectors, lawn mowers, automated harvesters, and window cleaners. In this paper, a novel neural network approach is proposed for complete coverage path planning with obstacle avoidance of cleaning robots in nonstationary environments. The dynamics of each neuron in the topologically organized neural network is characterized by a shunting equation derived from Hodgkin and Huxley's (1952) membrane equation. There are only local lateral connections among neurons. The robot path is autonomously generated from the dynamic activity landscape of the neural network and the previous robot location. The proposed model algorithm is computationally simple. Simulation results show that the proposed model is capable of planning collision-free complete coverage robot paths.
---
paper_title: A subdivision algorithm in configuration space for findpath with rotation

paper_content:

A recursive cellular representation for configuration space is presented along with an algorithm for searching that space for collision-free paths. The details of the algorithm are presented for polygonal obstacles and a moving object with two translational and one rotational degrees of freedom.
---
paper_title: Real-time obstacle avoidance for manipulators and mobile robots

paper_content:

This paper presents a unique real-time obstacle avoidance approach for manipulators and mobile robots based on the "artificial potential field" concept. In this approach, collision avoidance, traditionally considered a high level planning problem, can be effectively distributed between different levels of control, allowing real-time robot operations in a complex environment. We have applied this obstacle avoidance scheme to robot arm using a new approach to the general problem of real-time manipulator control. We reformulated the manipulator control problem as direct control of manipulator motion in operational space-the space in which the task is originally described-rather than as control of the task's corresponding joint space motion obtained only after geometric and kinematic transformation. This method has been implemented in the COSMOS system for a PUMA 560 robot. Using visual sensing, real-time collision avoidance demonstrations on moving obstacles have been performed.
---
paper_title: Robot Motion Planning: A Distributed Representation Approach

paper_content:

We propose a new approach to robot path planning that consists of building and searching a graph connecting the local minima of a potential function defined over the robot's configuration space. A planner based on this approach has been implemented. This planner is consider ably faster than previous path planners and solves prob lems for robots with many more degrees of freedom (DOFs). The power of the planner derives both from the "good" properties of the potential function and from the efficiency of the techniques used to escape the local min ima of this function. The most powerful of these tech niques is a Monte Carlo technique that escapes local min ima by executing Brownian motions. The overall approach is made possible by the systematic use of distributed rep resentations (bitmaps) for the robot's work space and configuration space. We have experimented with the plan ner using several computer-simulated robots, including rigid objects with 3 DOFs (in 2D work space) and 6 DOFs (in 3D work space) and ...
---
paper_title: RRT-connect: An efficient approach to single-query path planning

paper_content:

A simple and efficient randomized algorithm is presented for solving single-query path planning problems in high-dimensional configuration spaces. The method works by incrementally building two rapidly-exploring random trees (RRTs) rooted at the start and the goal configurations. The trees each explore space around them and also advance towards each other through, the use of a simple greedy heuristic. Although originally designed to plan motions for a human arm (modeled as a 7-DOF kinematic chain) for the automatic graphic animation of collision-free grasping and manipulation tasks, the algorithm has been successfully applied to a variety of path planning problems. Computed examples include generating collision-free motions for rigid objects in 2D and 3D, and collision-free manipulation motions for a 6-DOF PUMA arm in a 3D workspace. Some basic theoretical analysis is also presented.
---
paper_title: Reducing metric sensitivity in randomized trajectory design

paper_content:

This paper addresses the trajectory design for generic problems that involve: (1) complicated global constraints that include nonconvex obstacles, (2) nonlinear equations of motion that involve substantial drift due to momentum, and (3) a high-dimensional state space. Our approach to these challenging problems is to develop randomized planning algorithms based on rapidly-exploring random trees (RRTs). RRTs use metric-induced heuristics to conduct a greedy exploration of the state space; however, performance substantially degrades when the chosen metric does not adequately reflect the true cost-to-go. In this paper, we present a version of the RRT that refines its exploration strategy in the presence of a poor metric. Experiments on problems in vehicle dynamics and spacecraft navigation indicate substantial performance improvement over existing techniques.
---
paper_title: Sampling-Based Real-Time Motion Planning under State Uncertainty for Autonomous Micro-Aerial Vehicles in GPS-Denied Environments

paper_content:

This paper presents a real-time motion planning approach for autonomous vehicles with complex dynamics and state uncertainty. The approach is motivated by the motion planning problem for autonomous vehicles navigating in GPS-denied dynamic environments, which involves non-linear and/or non-holonomic vehicle dynamics, incomplete state estimates, and constraints imposed by uncertain and cluttered environments. To address the above motion planning problem, we propose an extension of the closed-loop rapid belief trees, the closed-loop random belief trees (CL-RBT), which incorporates predictions of the position estimation uncertainty, using a factored form of the covariance provided by the Kalman filter-based estimator. The proposed motion planner operates by incrementally constructing a tree of dynamically feasible trajectories using the closed-loop prediction, while selecting candidate paths with low uncertainty using efficient covariance update and propagation. The algorithm can operate in real-time, continuously providing the controller with feasible paths for execution, enabling the vehicle to account for dynamic and uncertain environments. Simulation results demonstrate that the proposed approach can generate feasible trajectories that reduce the state estimation uncertainty, while handling complex vehicle dynamics and environment constraints.
---
paper_title: Incremental Sampling-based Algorithms for Optimal Motion Planning

paper_content:

During the last decade, incremental sampling-based motion planning algorithms, such as the Rapidly-exploring Random Trees (RRTs), have been shown to work well in practice and to possess theoretical guarantees such as probabilistic completeness. However, no theoretical bounds on the quality of the solution obtained by these algorithms, e.g., in terms of a given cost function, have been established so far. The purpose of this paper is to fill this gap, by designing efficient incremental samplingbased algorithms with provable optimality properties. The first contribution of this paper is a negative result: it is proven that, under mild technical conditions, the cost of the best path returned by RRT converges almost surely to a non-optimal value, as the number of samples increases. Second, a new algorithm is considered, called the Rapidly-exploring Random Graph (RRG), and it is shown that the cost of the best path returned by RRG converges to the optimum almost surely. Third, a tree version of RRG is introduced, called RRT∗, which preserves the asymptotic optimality of RRG while maintaining a tree structure like RRT. The analysis of the new algorithms hinges on novel connections between sampling-based motion planning algorithms and the theory of random geometric graphs. In terms of computational complexity, it is shown that the number of simple operations required by both the RRG and RRT∗ algorithms is asymptotically within a constant factor of that required by RRT.
---
paper_title: Incremental sampling-based algorithm for risk-aware planning under motion uncertainty

paper_content:

This paper considers the problem of motion planning for linear systems subject to Gaussian motion noise and proposes a risk-aware planning algorithm: CC-RRT*-D. The proposed CC-RRT*-D employs the chance-constraint approximation and leverages the asymptotically optimal property of RRT* framework to compute risk-aware and asymptotically optimal trajectories. By explicitly considering the state dependence for prior state estimate, the over-conservative problem of chance-constraint approximation can be provably solved. Computational experiment results show that CC-RRT*-D is efficient and robust compared with related algorithms. The real-time experiment on an autonomous vehicle shows that our proposed algorithm is applicable to real-time obstacle avoidance.
---
paper_title: Chance Constrained RRT for Probabilistic Robustness to Environmental Uncertainty

paper_content:

between planner conservatism and the risk of infeasibility. This paper presents a novel real-time planning algorithm, chance constrained rapidly-exploring random trees (CC-RRT), which uses chance constraints to guarantee probabilistic feasibility for linear systems subject to process noise and/or uncertain, possibly dynamic obstacles. By using RRT, the algorithm enjoys the computational benets of sampling-based algorithms, such as trajectory-wise constraint checking and incorporation of heuristics, while explicitly incorporating uncertainty within the formulation. Under the assumption of Gaussian noise, probabilistic feasibility at each time step can be established through simple simulation of the state conditional mean and the evaluation of linear constraints. Alternatively, a small amount of additional computation can be used to explicitly compute a less conservative probability bound at each time step. Simulation results show that this algorithm can be used for ecient identication and execution of probabilistically safe paths in real time.
---
paper_title: Real-Time Motion Planning for Agile Autonomous Vehicles

paper_content:

Planning the path of an autonomous, agile vehicle in a dynamic environment is a very complex problem, especially when the vehicle is required to use its full maneuvering capabilities. Recent efforts aimed at using randomized algorithms for planning the path of kinematic and dynamic vehicles have demonstrated considerable potential for implementation on future autonomous platforms. This paper builds upon these efforts by proposing a randomized path planning architecture for dynamical systems in the presence of fixed and moving obstacles. This architecture addresses the dynamic constraints on the vehicle's motion, and it provides at the same time a consistent decoupling between low-level control and motion planning. The path planning algorithm retains the convergence properties of its kinematic counterparts. System safety is also addressed in the face of finite computation times by analyzing the behavior of the algorithm when the available onboard computation resources are limited, and the planning must be performed in real time. The proposed algorithm can be applied to vehicles whose dynamics are described either by ordinary differential equations or by higher-level, hybrid representations. Simulation examples involving a ground robot and a small autonomous helicopter are presented and discussed.
---
paper_title: Safe Multirobot Navigation Within Dynamics Constraints

paper_content:

This paper introduces a refinement of the classical sense-plan-act objective maximization method for setting agent goals, a real-time randomized path planner, a bounded acceleration motion control system, and a randomized velocity-space search for collision avoidance of multiple moving robotic agents. We have found this approach to work well for dynamic and unpredictable domains requiring real-time response and flexible coordination of multiple agents. First, the approach employs randomized search for objective maximization and motion planning, allowing real-time or any-time performance. Next, a novel cooperative safety algorithm is employed which respects agent dynamics limitations while also preventing collisions with static obstacles or other participating agents. An implementation of our multilayer approach has been tested and validated on real robots, forming the basis for an autonomous robotic soccer team
---
paper_title: Efficient Sampling-Based Motion Planning for On-Road Autonomous Driving

paper_content:

This paper introduces an efficient motion planning method for on-road driving of the autonomous vehicles, which is based on the rapidly exploring random tree (RRT) algorithm. RRT is an incremental sampling-based algorithm and is widely used to solve the planning problem of mobile robots. However, due to the meandering path, the inaccurate terminal state, and the slow exploration, it is often inefficient in many applications such as autonomous vehicles. To address these issues and considering the realistic context of on-road autonomous driving, we propose a fast RRT algorithm that introduces a rule-template set based on the traffic scenes and an aggressive extension strategy of search tree. Both improvements lead to a faster and more accurate RRT toward the goal state compared with the basic RRT algorithm. Meanwhile, a model-based prediction postprocess approach is adopted, by which the generated trajectory can be further smoothed and a feasible control sequence for the vehicle would be obtained. Furthermore, in the environments with dynamic obstacles, an integrated approach of the fast RRT algorithm and the configuration-time space can be used to improve the quality of the planned trajectory and the replanning. A large number of experimental results illustrate that our method is fast and efficient in solving planning queries of on-road autonomous driving and demonstrate its superior performances over previous approaches.
---
paper_title: Current Issues in Sampling-Based Motion Planning

paper_content:

In this paper, we discuss the field of sampling-based motion planning. In contrast to methods that construct boundary representations of configuration space obstacles, samplingbased methods use only information from a collision detector as they search the configuration space. The simplicity of this approach, along with increases in computation power and the development of efficient collision detection algorithms, has resulted in the introduction of a number of powerful motion planning algorithms, capable of solving challenging problems with many degrees of freedom. First, we trace how sampling-based motion planning has developed. We then discuss a variety of important issues for sampling-based motion planning, including uniform and regular sampling, topological issues, and search philosophies. Finally, we address important issues regarding the role of randomization in sampling-based motion planning.
---
paper_title: Sampling-Based Robot Motion Planning: A Review

paper_content:

Motion planning is a fundamental research area in robotics. Sampling-based methods offer an efficient solution for what is otherwise a rather challenging dilemma of path planning. Consequently, these methods have been extended further away from basic robot planning into further difficult scenarios and diverse applications. A comprehensive survey of the growing body of work in sampling-based planning is given here. Simulations are executed to evaluate some of the proposed planners and highlight some of the implementation details that are often left unspecified. An emphasis is placed on contemporary research directions in this field. We address planners that tackle current issues in robotics. For instance, real-life kinodynamic planning, optimal planning, replanning in dynamic environments, and planning under uncertainty are discussed. The aim of this paper is to survey the state of the art in motion planning and to assess selected planners, examine implementation details and above all shed a light on the current challenges in motion planning and the promising approaches that will potentially overcome those problems.
---
paper_title: Multilevel Path Planning for Nonholonomic Robots Using Semiholonomic Subsystems

paper_content:

We present a new and complete multilevel approachfor solving path- planning problems for nonholonomic robots. At the first level, a path is found that disrespects (some of) the nonholonomic constraints. At each of the next levels, a new path is generated by transformation of the path generated at the previous level. The transformation is such that more nonholonomic constraints are respected than at the previous level. At the final level, all nonholonomic constraints are respected. We present two techniques for these transformations. The first, which we call the pick and link technique, repeatedly picks pieces from the given path, and tries to replace them by more feasible ones. The second technique restricts the free configuration space to a "tube" around the given path, and a road map that captures the free-space connectivity within this tube is constructed by the prob abilistic path planner. From this road map we retrieve a new, more feasible path. In the intermediate levels, we plan paths for what we refer to as semiholonomic subsystems. Such systems are obtained by taking real (physical) systems, and removing some of their nonholonomic constraints. In this paper, we apply the scheme to carlike robots pulling trail ers, that is, tractor-trailer robots. In this case, the real system is the tractor-trailer robot, and the ignored constraints in the semiholo nomic subsystems are the kinematic ones on the trailers. These are the constraints of rolling without slipping, on the trailer's wheels. Experimental results are given that illustrate the time efficiency of the resulting planner. In particular, we show that using the multilevel scheme leads to significantly better performance (in computation time and path shape) than direct transformations to feasible paths.
---
paper_title: Guided RRT: A greedy search strategy for kinodynamic motion planning

paper_content:

Sampling-based methods, such as Probabilistic Roadmap Method(PRM)[l], Rapidly-Exploring Random Tree(RRT)[2], have been proposed as promising solutions for kinodynamic problems. Nevertheless, it's still a challenge for practical application especially for complex systems. In particular, most of the forward propagation is fruitless, which lead to heavy computation and be time-consuming. This paper presents a greedy kinodynamic motion planner: Guided RRT. The main characteristics are that the environments are explored by Geometric trees previously and nodes near the geometric feasible path enjoy more preference. Instead of exploring the environments uniformly, the new approach expands towards the goal greedily along a series of waypoints, with probabilistically completeness. And to guarantee the effective of the greed, a new distance metric based on Euclidean metric are proposed by considering both the current position and the following position with zero-input. We compare our technique with standard RRT and show that it achieves favorable performance when planning under kinodynamic constraints.
---
paper_title: Sampling-Based Robot Motion Planning: A Review

paper_content:

Motion planning is a fundamental research area in robotics. Sampling-based methods offer an efficient solution for what is otherwise a rather challenging dilemma of path planning. Consequently, these methods have been extended further away from basic robot planning into further difficult scenarios and diverse applications. A comprehensive survey of the growing body of work in sampling-based planning is given here. Simulations are executed to evaluate some of the proposed planners and highlight some of the implementation details that are often left unspecified. An emphasis is placed on contemporary research directions in this field. We address planners that tackle current issues in robotics. For instance, real-life kinodynamic planning, optimal planning, replanning in dynamic environments, and planning under uncertainty are discussed. The aim of this paper is to survey the state of the art in motion planning and to assess selected planners, examine implementation details and above all shed a light on the current challenges in motion planning and the promising approaches that will potentially overcome those problems.
---
paper_title: Systematic Reviews in the Social Sciences : A Practical Guide

paper_content:

Such diverse thinkers as Lao-Tze, Confucius, and U.S. Defense Secretary Donald Rumsfeld have all pointed out that we need to be able to tell the difference between real and assumed knowledge. The systematic review is a scientific tool that can help with this difficult task. It can help, for example, with appraising, summarising, and communicating the results and implications of otherwise unmanageable quantities of data. This is important because quite often there are so many studies, and their results are often so conflicting, that no policymaker or practitioner could possibly carry out this task themselves.Systematic review methods have been widely used in health care, and are becoming increasingly common in the social sciences (fostered, for example, by the work of the Campbell Collaboration). ::: ::: This book outlines the rationale and methods of systematic reviews, giving worked examples from social science and other fields. It requires no previous knowledge, but takes the reader through the process stage by stage. It draws on examples from such diverse fields as psychology, criminology, education, transport, social welfare, public health, and housing and urban policy, among others.The book includes detailed sections on assessing the quality of both quantitative, and qualitative research; searching for evidence in the social sciences;meta-analytic and other methods of evidence synthesis; publication bias; heterogeneity; and approaches to dissemination.
---
paper_title: Optimal Path Planning using RRT* based Approaches: A Survey and Future Directions

paper_content:

Optimal path planning refers to find the collision free, shortest, and smooth route between start and goal positions. This task is essential in many robotic applications such as autonomous car, surveillance operations, agricultural robots, planetary and space exploration missions. Rapidly-exploring Random Tree Star (RRT*) is a renowned sampling based planning approach. It has gained immense popularity due to its support for high dimensional complex problems. A significant body of research has addressed the problem of optimal path planning for mobile robots using RRT* based approaches. However, no updated survey on RRT* based approaches is available. Considering the rapid pace of development in this field, this paper presents a comprehensive review of RRT* based path planning approaches. Current issues relevant to noticeable advancements in the field are investigated and whole discussion is concluded with challenges and future research directions.
---
paper_title: Steps toward derandomizing RRTs

paper_content:

We present two new motion planning algorithms, based on the rapidly exploring random tree (RRT) family of algorithms. These algorithms represent the first work in the direction of derandomizing RRTs; this is a very challenging problem due to the way randomization is used in RRTs. In RRTs, randomization is used to create Voronoi bias, which causes the search trees to rapidly explore the state space. Our algorithms take steps to increase the Voronoi bias and to retain this property without the use of randomization. Studying these and related algorithms would improve our understanding of how efficient exploration can be accomplished, and would hopefully lead to improved planners. We give experimental results that illustrate how the new algorithms explore the state space and how they compare with existing RRT algorithms.
---
paper_title: Incrementally reducing dispersion by increasing Voronoi bias in RRTs

paper_content:

We discuss theoretical and practical issues related to using Rapidly-Exploring Random Trees (RRTs) to incrementally reduce dispersion in the configuration space. The original RRT planners use randomization to create Voronoi bias, which causes the search trees to rapidly explore the state space. We introduce RRT-like planners based on exact Voronoi diagram computation, as well as sampling-based algorithms which approximate their behavior. We give experimental results illustrating how the new algorithms explore the configuration space and how they compare with existing RRT algorithms. Initial results show that our algorithms are advantageous compared to existing RRTs, especially with respect to the number of collision checks and nodes in the search tree.
---
paper_title: Informed RRT*: Optimal Sampling-based Path Planning Focused via Direct Sampling of an Admissible Ellipsoidal Heuristic

paper_content:

Rapidly-exploring random trees (RRTs) are pop- ular in motion planning because they find solutions efficiently to single-query problems. Optimal RRTs (RRT*s) extend RRTs to the problem of finding the optimal solution, but in doing so asymptotically find the optimal path from the initial state to every state in the planning domain. This behaviour is not only inefficient but also inconsistent with their single-query nature. For problems seeking to minimize path length, the subset of states that can improve a solution can be described by a prolate hyperspheroid. We show that unless this subset is sam- pled directly, the probability of improving a solution becomes arbitrarily small in large worlds or high state dimensions. In this paper, we present an exact method to focus the search by directly sampling this subset. The advantages of the presented sampling technique are demonstrated with a new algorithm, Informed RRT*. This method retains the same probabilistic guarantees on complete- ness and optimality as RRT* while improving the convergence rate and final solution quality. We present the algorithm as a simple modification to RRT* that could be further extended by more advanced path-planning algorithms. We show exper- imentally that it outperforms RRT* in rate of convergence, final solution cost, and ability to find difficult passages while demonstrating less dependence on the state dimension and range of the planning problem.
---
paper_title: Planning with ants: Efficient path planning with rapidly exploring random trees and ant colony optimization

paper_content:

Rapidly exploring random trees (RRTs) have been proven to be efficient for planning in environments populated with obstacles. These methods perform a uniform sampling of the state space, which is needed to guarantee the algorithm’s completeness but does not necessarily lead to the most efficient solution. In previous works it has been shown that the use of heuristics to modify the sampling strategy could incur an improvement in the algorithm performance. However, these heuristics only apply to solve the shortest path-planning problem. Here we propose a framework that allows us to incorporate arbitrary heuristics to modify the sampling strategy according to the user requirements. This framework is based on ‘learning from experience’. Specifically, we introduce a utility function that takes the contribution of the samples to the tree construction into account; sampling at locations of increased utility then becomes more frequent. The idea is realized by introducing an ant colony optimization concept in the RRT/RRT* algorithm and defining a novel utility function that permits trading off exploitation versus exploration of the state space. We also extend the algorithm to allow an anytime implementation. The scheme is validated with three scenarios: one populated with multiple rectangular obstacles, one consisting of a single narrow passage and a maze-like environment. We evaluate its performance in terms of the cost and time to find the first path, and in terms of the evolution of the path quality with the number of iterations. It is shown that the proposed algorithm greatly outperforms state-of-the-art RRT and RRT* algorithms.
---
paper_title: Sampling-Based Robot Motion Planning: A Review

paper_content:

Motion planning is a fundamental research area in robotics. Sampling-based methods offer an efficient solution for what is otherwise a rather challenging dilemma of path planning. Consequently, these methods have been extended further away from basic robot planning into further difficult scenarios and diverse applications. A comprehensive survey of the growing body of work in sampling-based planning is given here. Simulations are executed to evaluate some of the proposed planners and highlight some of the implementation details that are often left unspecified. An emphasis is placed on contemporary research directions in this field. We address planners that tackle current issues in robotics. For instance, real-life kinodynamic planning, optimal planning, replanning in dynamic environments, and planning under uncertainty are discussed. The aim of this paper is to survey the state of the art in motion planning and to assess selected planners, examine implementation details and above all shed a light on the current challenges in motion planning and the promising approaches that will potentially overcome those problems.
---
paper_title: Current Issues in Sampling-Based Motion Planning

paper_content:

In this paper, we discuss the field of sampling-based motion planning. In contrast to methods that construct boundary representations of configuration space obstacles, samplingbased methods use only information from a collision detector as they search the configuration space. The simplicity of this approach, along with increases in computation power and the development of efficient collision detection algorithms, has resulted in the introduction of a number of powerful motion planning algorithms, capable of solving challenging problems with many degrees of freedom. First, we trace how sampling-based motion planning has developed. We then discuss a variety of important issues for sampling-based motion planning, including uniform and regular sampling, topological issues, and search philosophies. Finally, we address important issues regarding the role of randomization in sampling-based motion planning.
---
paper_title: Informed RRT*: Optimal Sampling-based Path Planning Focused via Direct Sampling of an Admissible Ellipsoidal Heuristic

paper_content:

Rapidly-exploring random trees (RRTs) are pop- ular in motion planning because they find solutions efficiently to single-query problems. Optimal RRTs (RRT*s) extend RRTs to the problem of finding the optimal solution, but in doing so asymptotically find the optimal path from the initial state to every state in the planning domain. This behaviour is not only inefficient but also inconsistent with their single-query nature. For problems seeking to minimize path length, the subset of states that can improve a solution can be described by a prolate hyperspheroid. We show that unless this subset is sam- pled directly, the probability of improving a solution becomes arbitrarily small in large worlds or high state dimensions. In this paper, we present an exact method to focus the search by directly sampling this subset. The advantages of the presented sampling technique are demonstrated with a new algorithm, Informed RRT*. This method retains the same probabilistic guarantees on complete- ness and optimality as RRT* while improving the convergence rate and final solution quality. We present the algorithm as a simple modification to RRT* that could be further extended by more advanced path-planning algorithms. We show exper- imentally that it outperforms RRT* in rate of convergence, final solution cost, and ability to find difficult passages while demonstrating less dependence on the state dimension and range of the planning problem.
---
paper_title: Self-learning RRT* Algorithm for Mobile Robot Motion Planning in Complex Environments

paper_content:

RRT* is a practical and efficient incremental sampling-based motion planning algorithm. However, its searching ability is quite inefficient in some cases, due to relying on uniform random sampling like other RRT-based algorithms without taking the environment information and prior knowledge into account, which particularly leads to many sampling failures or generation of useless nodes in complex environments. In this paper, we propose an extension of RRT* based on a self-learning strategy and a hybrid-biased sampling scheme to improve the planning efficiency. By taking advantage of the prior knowledge accumulation and cost estimation, the searching tree has higher probability and success rate to extend in difficult areas. We also demonstrate the performance of our algorithm by building some simulation environments for our mobile robot and conclude with the results compared with RRT*.
---
paper_title: Goal Directed Approach to Autonomous Motion Planning for Unmanned Vehicles

paper_content:

Advancement in the field of autonomous motion planning has enabled the realisation of fully autonomous unmanned vehicles. Sampling based motion planning algorithms have shown promising prospects in generating fast, effective and practical solutions to different motion planning problems in unmanned vehicles for both civilian and military applications. But the goal bias introduced by heuristic probability shaping to generate faster solution may result in local collisions. A simple, real-time method is proposed for goal direction by preferential selection of a state from a sampled pair of random state, based on the distance to goal. This limits the graph motions resulting in smaller data structure, making the algorithm optimised for time and solution length. This would enable unmanned vehicles to take shorter paths and avoid collisions in obstacle rich environment. The approach is analysed on a sampling based algorithm, rapidly-exploring random tree (RRT) which computes motion plans under constrain of time. This paper proposes an algorithm called ’goal directed RRT (GRRT)’ building on the basic RRT algorithm, providing an alternative to probabilistic goal biasing, thereby avoiding local collision. The approach is evaluated by benchmarking it with RRT algorithm for kinematic car, dynamic car and a quadrotor and the results show improvements in length of the motion plans and the time of computing.
---
paper_title: A kind of two-stage RRT algorithm for robotic path planning

paper_content:

In order to solve the problem of motion planning with dynamics, RRT algorithm was proposed. But with the environment becoming complex, the tree exploration slows down significantly. In this paper, a novel two-stage motion planning is proposed. The first stage is discrete search based on the scent pervasion principle, and the second stage is the sampling-based motion planning under the direction of the scent information. The results show the good performance and convergence speed of the proposed algorithm.
---
paper_title: A random sampling-based approach to goal-directed footstep planning for humanoid robots

paper_content:

Global path planning and navigation strategies for humanoid robots are different from those for mobile robots, since humanoid robots can step over or upon some obstacles. Sampling-based footstep planning is a goal-directed navigation approach for humanoid robots which considers both this unique locomotion capability and the global environment information. However, existing humanoid footstep planning methods are based on deterministic sampling strategies, which make them not practical in some special environments, such as areas with local minima or narrow passages. In order to improve the completeness of sampling-based footstep planning in the above environments, we propose a random sampling-based footstep planning approach based on rapidly-exploring random trees, which termed as Multi-RRT footstep planner. We also apply a goal-biased non-uniform strategy in order to improve the convergence rate of the Multi-RRT footstep planner. The proposed random sampling approach is verified by comparison with deterministic approach in numerical planning experiments.
---
paper_title: Design and implementation of improved RRT algorithm for collision free motion planning of high-dimensional robot in complex environment

paper_content:

According to the collision free motion planning of high-dimensional robot in the complex environment, the improved RRT algorithm is proposed. First of all, collision detection algorithm is put forward on the basis of OBB by using Separating Axis principle. Secondly, the basic RRT algorithm concept is studied, and by integrating J-Space sampling and C-Space modeling technology, the improved RRT algorithm that can promote the stability of performance and convergence rate is put forward; the collision detection algorithm proposed in this paper is integrated into the improved RRT algorithm to judge whether the robot in C-Space collides with the obstacles. Finally, a three-dimensional system software framework is designed and achieved, and the effectiveness and stability proposed in this paper is verified via computational simulation.
---
paper_title: Sampling-based path planning with goal oriented sampling

paper_content:

Path planning in complicated environments is a time consuming and computationally expensive task. Especially in high-dimensional configuration spaces with complex obstacles, searching for a proper path while avoiding collisions is still challenging. This paper presents an improved sampling-based algorithm, called the Goal Oriented sampling method (GO sampling) that quickly generates an initial solution overcoming these problems. GO sampling extends the sampling method of the Rapidly-exploring Random Tree (RRT) algorithm. GO sampling is able to identify the initial solution in a shorter time than that of the RRT algorithm and shows significant improvement in computational efficiency. The algorithm is evaluated with simulations in 2D and 3D space.
---
paper_title: Goal-oriented stimulus generation for analog circuits

paper_content:

We present a methodology to generate goal-oriented test cases for verifying nonlinear analog circuits. We use a learning-based approach to identify the goal regions in circuit's state space. We use the information that we learn to guide the growth of Rapidly-exploring Random Trees (RRTs) towards these goal regions. Compared to previous approaches for test generation, our methodology generates several test cases of the circuit that are more concentrated in the relevant operating regions. We demonstrate the effectiveness of our approach on typical case studies. We show that our methodology can be used to generate test cases for undesirable behavior that was previously hard to detect.
---
paper_title: Potentially Guided Bidirectionalized RRT* for Fast Optimal Path Planning in Cluttered Environments

paper_content:

Abstract Rapidly-exploring Random Tree star (RRT*) has recently gained immense popularity in the motion planning community as it provides a probabilistically complete and asymptotically optimal solution without requiring the complete information of the obstacle space. In spite of all of its advantages, RRT* converges to optimal solution very slowly. Hence to improve the convergence rate, its bidirectional variants were introduced, the Bi-directional RRT* (B-RRT*) and Intelligent Bi-directional RRT* (IB-RRT*). However, as both variants perform pure exploration, they tend to suffer in highly cluttered environments. In order to overcome these limitations we introduce a new concept of potentially guided bidirectional trees in our proposed Potentially Guided Intelligent Bi-directional RRT* (PIB-RRT*) and Potentially Guided Bi-directional RRT* (PB-RRT*). The proposed algorithms greatly improve the convergence rate and have a more efficient memory utilization. Theoretical and experimental evaluation of the proposed algorithms have been made and compared to the latest state of the art motion planning algorithms under different challenging environmental conditions and have proven their remarkable improvement in efficiency and convergence rate.
---
paper_title: Multipartite RRTs for Rapid Replanning in Dynamic Environments

paper_content:

The rapidly-exploring random tree (RRT) algorithm has found widespread use in the field of robot motion planning because it provides a single-shot, probabilistically complete planning method which generalizes well to a variety of problem domains. We present the multipartite RRT (MP-RRT), an RRT variant which supports planning in unknown or dynamic environments. By purposefully biasing the sampling distribution and re-using branches from previous planning iterations, MP-RRT combines the strengths of existing adaptations of RRT for dynamic motion planning. Experimental results show MP-RRT to be very effective for planning in dynamic environments with unknown moving obstacles, replanning in high-dimensional configuration spaces, and replanning for systems with space time constraints.
---
paper_title: Potential Functions based Sampling Heuristic For Optimal Path Planning

paper_content:

Rapidly-exploring Random Tree star (RRT*) is a recently proposed extension of Rapidly-exploring Random Tree (RRT) algorithm that provides a collision-free, asymptotically optimal path regardless of obstacles geometry in a given environment. However, one of the limitation in the RRT* algorithm is slow convergence to optimal path solution. As a result it consumes high memory as well as time due to the large number of iterations utilised in achieving optimal path solution. To overcome these limitations, we propose the potential function based-RRT* that incorporates the artificial potential field algorithm in RRT*. The proposed algorithm allows a considerable decrease in the number of iterations and thus leads to more efficient memory utilization and an accelerated convergence rate. In order to illustrate the usefulness of the proposed algorithm in terms of space execution and convergence rate, this paper presents rigorous simulation based comparisons between the proposed techniques and RRT* under different environmental conditions. Moreover, both algorithms are also tested and compared under non-holonomic differential constraints.
---
paper_title: A rapidly exploring random tree optimization algorithm for space robotic manipulators guided by obstacle avoidance independent potential field

paper_content:

The crucial problem of obstacle avoidance path planning is to realize both reducing the operational cost and improving its efficiency. A rapidly exploring random tree optimization algorithm for spa...
---
paper_title: An improved RRT algorithm incorporating obstacle boundary information

paper_content:

Rapidly-Exploring Random Trees (RRT) is a sampling-based path planning method, which aims at finding the feasible path using a randomized data structure. But RRT usually can not find the optimal path. Although RRT* is an asymptotically optimal algorithm, its planning time scales poorly. In this paper, we propose an improved RRT algorithm incorporating obstacle boundary information to deal with these two problems. We classify obstacles in the environment into valuable and valueless obstacles. For the obstacle placed between the start and goal positions, it is regarded as valuable and we use its boundary information to make the path planner sample points around it to avoid other bad sampling points. Then the random tree will grow more intentionally to the goal position. By applying Partially Observed Markov Decision Process (POMDP) in our algorithm, we also can prove in theory that obstacle boundary information really improves RRT algorithm. In our experiments, we show that our algorithm can find a better feasible path faster than RRT.
---
paper_title: Random Triangle Sampling Path Planning of Assembly/Disassembly in Environment with Dangerzones

paper_content:

To solve the assembly/disassembly path planning in the environment with danger zones, a RRT-based path planning algorithm was presented. The algorithm addressed a random sampling function which obtains random state from the triangles that describe the dangerzones. The local planner connecting the samples with RRT tree is also introduced. Experimental results show that the algorithm much more effectively searches the paths between dangerzones and obstacles.
---
paper_title: Obstacle-guided informed planning towards robot navigation in cluttered environments

paper_content:

Informed sampling, a sampling method that focuses the search by sampling the subset of states that potentially improve the current solution, has been adopted in path-planning algorithms like Informed RRT∗ [1] and its successor, Batch Informed Trees (BIT∗) [2], for speeding up the convergence and improving the quality of solution. In this paper, we consider the problem of path planning in cluttered environments containing narrow passages. We build as an extension to BIT∗ our obstacle-guided sampling and biasing strategy. With a neighbourhood sampling step, we embed obstacle-based Gaussian sampling in the underlying uniform sampling, which gives rise to the sample density in difficult-to-sample homotopy classes. The local obstacle information is implicitly extracted with simple heuristics to recognize “navigators” that belong to narrow passages, and to inform the planner for subsequent sample biasing, so that the convergence of the solution towards optimum can be locally accelerated leveraging obstacle information. Our strategy combines the exploratory advantage of uniform informed sampling and the exploitative feature of obstacle-based Gaussian sampling, while retaining the asymptotic sample coverage of the free space to search for the global optimal solution. We apply such customization of the BIT∗ algorithm to robot navigation path planning instances and demonstrate hte improved planning efficiency in 2D and 3D cluttered environments with narrow passages.
---
paper_title: Triangle Sampling Path Planning in Environment with Danger Zones for Assembly/Disassembly

paper_content:

To plan a feasible path in the environment with danger zones for assembly/disassembly, a RRT-based path planning algorithm was presented. The algorithm addressed a new density avoided sampling function based on kurtosis coefficient for planning in the free configuration space, and introduced a random sampling function which obtains random state from the triangles that describe the danger zones. The local planner connecting the samples with RRT trees is also introduced. Experimental results show that the algorithm much more effectively searches the paths between danger zones and obstacles. Streszczenie. Zaprezentowano metode wyznaczania mozliwej ściezki ruchu w środowisku z zagrozeniami. Algorytm bazuje na systemie PRM (probabilistic roadmap) i RRT (rapidly-exploring random trees). (Planowanie drogi w środowisku z zagrozeniami przy probkowaniu trojkątnym)
---
paper_title: RRT-based nonholonomic motion planning using any-angle path biasing

paper_content:

RRT and RRT* have become popular planning techniques, in particular for high-dimensional systems such as wheeled robots with complex nonholonomic constraints. Their planning times, however, can scale poorly for such robots, which has motivated researchers to study hierarchical techniques that grow the RRT trees in more focused ways. Along this line, we introduce Theta*-RRT that hierarchically combines (discrete) any-angle search with (continuous) RRT motion planning for nonholonomic wheeled robots. Theta*-RRT is a variant of RRT that generates a trajectory by expanding a tree of geodesics toward sampled states whose distribution summarizes geometric information of the any-angle path. We show experimentally, for both a differential drive system and a high-dimensional truck-and-trailer system, that Theta*-RRT finds shorter trajectories significantly faster than four baseline planners (RRT, A*-RRT, RRT*, A*-RRT*) without loss of smoothness, while A*-RRT* and RRT* (and thus also Informed RRT*) fail to generate a first trajectory sufficiently fast in environments with complex nonholonomic constraints. We also prove that Theta*-RRT retains the probabilistic completeness of RRT for all small-time controllable systems that use an analytical steer function.
---
paper_title: Path planning combining improved rapidly-exploring random trees with dynamic window approach in ROS

paper_content:

Path planning is a fundamental research area in robotics. Sampling-based methods have been extended further away from basic robot planning into further difficult scenarios and diverse applications for their efficient solution. Issues occurred where they only offer a path rather than velocity commands; the changing situation of environment is hard to tackle. This paper presents a novel integrated approach of creating path for robot navigation with dynamic constrains. In the proposed algorithm, a biased Rapidly-Exploring Random Trees (RRT) is utilized to find a global path in the configuration space. Then, the Dynamic Window Approach (DWA) is performed over the path to calculate translational and rotational velocity commands for the robot. Performance of the proposed method is tested and validated using Robot Operating System (ROS). Simulations show that the proposed methodology achieves efficient and smooth path for the robot under the dynamic constrains.
---
paper_title: Tunnel detection in protein structures using sampling-based motion planning

paper_content:

Proteins are involved in many biochemical processes. The behavior of proteins is influenced by internal void space such as tunnels or cavities. Tunnels are paths leading from an inner protein active site to its surface. The knowledge about tunnels and their evolution over time provides an insight into protein properties (e.g., stability). Sampling-based motion planning techniques like Rapidly Exploring Random Tree (RRT) can be used to find tunnels by sampling the corresponding configuration space. These methods can be easily adapted to operate with protein dynamics. The inner void space of proteins is very limited, which may decrease the ability of RRT to find a solution due to the narrow passage problem. In this paper, we propose to generate random samples using a Voronoi Diagram of the atoms. A subset of Voronoi vertices is dynamically maintained to support the generation of samples in promising regions inside the protein.
---
paper_title: Offline and Online Evolutionary Bi-Directional RRT Algorithms for Efficient Re-Planning in Dynamic Environments

paper_content:

This paper explores the use of evolutionary algorithms (EAs) to formulate additional biases for a probabilistic motion planner known as the rapidly exploring random tree (RRT) algorithm in environments with changing obstacle locations. An offline EA is utilized to produce a bias in an obstacle filled environment prior to rearranging the obstacles. It is demonstrated that the offline EA finds a bias reflecting the original environment and improves the RRT's efficiency during re-planning in environments with a small number of rearrangements. The rapidly exploring evolutionary tree (RET) algorithm is introduced as a hybrid RRT algorithm employing an online EA. It is demonstrated that the RET can improve the RRT's performance during re-planning in environments with many rearranged obstacles by exploiting characteristics of a balanced spatial kd-tree.
---
paper_title: Density Avoided Sampling: An Intelligent Sampling Technique for Rapidly-Exploring Random Trees

paper_content:

This paper proposes a new sampling procedure for rapidly-exploring random trees (RRT). In traditional path planning methods, sampling procedure is carried out by neglecting the configuration of environment. Hence useless samples tend to be generated; which will result in a waste of computational resources without any considerable improvement in the results. The sampling method proposed in this paper is based on the way that branches of plants grow in limited spaces. This method yields impressive improvements in the uniformity of expansion and the speed of space exploration for path planning queries in highly constrained environments wherein the visible Voronoi regions are largely affected by dense obstacles.
---
paper_title: A 2D Voronoi-Based Random Tree for Path Planning in Complicated 3D Environments

paper_content:

Path planning in complicated 3D environments with narrow passages and rooms is a challenging problem, which is usually time consuming for geometric searching methods or incomplete for sampling-based methods. Focusing on these issues, this paper presents a new algorithm named 2D Voronoi-based Random Tree which combines the completeness of the voronoi diagram based 2D path searching methods and the efficiency of sampling based path planning methods. In this method, 2D voronoi diagram is created and used to guide the growth of random trees in complicated 3D environments. In each iteration of random trees growth, a new node on voronoi edges is selected by moving forward to the target with a fix step length along edges. And then, the 3D particles are distributed locally around this node and be selected according to a cost function for the random trees growth. By doing so, this method can find a valid path in complicated 3D environments with narrow passages and rooms while improving its efficiency and completeness. To demonstrate its effectiveness, efficiency and robustness, the proposed method is examined and compared with RRT algorithm in various practical complex 3D environments.
---
paper_title: Steps toward derandomizing RRTs

paper_content:

We present two new motion planning algorithms, based on the rapidly exploring random tree (RRT) family of algorithms. These algorithms represent the first work in the direction of derandomizing RRTs; this is a very challenging problem due to the way randomization is used in RRTs. In RRTs, randomization is used to create Voronoi bias, which causes the search trees to rapidly explore the state space. Our algorithms take steps to increase the Voronoi bias and to retain this property without the use of randomization. Studying these and related algorithms would improve our understanding of how efficient exploration can be accomplished, and would hopefully lead to improved planners. We give experimental results that illustrate how the new algorithms explore the state space and how they compare with existing RRT algorithms.
---
paper_title: Extended RRT algorithm with dynamic N-dimensional cuboid domains

paper_content:

The paper presents an approach to path planning problem for manipulators operating in difficult environments with high probability of collisions. The approach improves the Rapidly exploring Random Trees (RRT) algorithm and produces a new approach with better results. It is achieved by expanding the forward and backward tree and reducing dynamically the sampling area of the free-configuration space (C-Space) by introducing a N-Dimensional cuboid regions. The place of this area could be dynamically or statically defined. The results show that this modification provides a very reasonable solution to the path planning problem applicable also to any kind of manipulators.
---
paper_title: Hybrid rule-based motion planner for mobile robot in cluttered workspace

paper_content:

Motion planning problem is an active field in robotics. It is concerned with converting high-level task specifications into low-level descriptions of how to move and provides a feasible sequence of movements that avoid obstacles while respecting kinematic and dynamic equations. In this work, new planners are designed with the aim of developing an efficient motion planner in a heterogeneous, cluttered, and dynamic workspace. The planners are composed of two layers, and they use a rule-based system as a guidance. The first layer uses exact cell decomposition method, which divides the workspace into manageable regions and finds the adjacency information for them. The second layer utilizes rapidly exploring random tree algorithm RRT that finds a solution in a cluttered workspace. The adjacency information of the free cells and the exploration information that is provided by RRT are combined and utilized to help the planners classifying the free regions and guiding the growth of RRT trees efficiently toward the most important areas. Two types of the planners are proposed, the first one uses adviser that pulls the trees' growth toward the boundary areas between explored and unexplored regions, while the adviser of the second planner uses the collision information and fuzzy rules to guide the trees' growth toward areas that have low collision rate around the boundaries of explored regions. The planners are tested in stationary as well as in changed workspace. The proposed methods have been compared to other approaches and the simulation results show that they yield better results in terms of completeness and efficiency.
---
paper_title: Obstacle space modeling and moving-window RRT for manipulator motion planning

paper_content:

A fast motion planner is presented for manipulator pick-and-place operation in cluttered workspace. This planner consists of two subalgorithms which are proposed to enhance the computational efficiency. First, based on the discretization and extraction of boundary surface from obstacle space, a new obstacle space modeling method is introduced to carry out the collision check promptly. Second, an optimized path searching subalgorithm named moving-window rapidly-exploring random tree is presented. The moving-window unilateral Gaussian random sampling strategy is used for fast convergence to the goal state in different environment. Finally, the proposed motion planner is simulated on a PUMA560 robot manipulator. The simulation results demonstrate that the proposed method enables real-time motion planning and can be implemented conveniently. More importantly, compared to the conventional methods, the developed method requires less storage space for obstacle space model, executes only once to check the collision rapidly for each segmented path. Besides, the stable performance in path searching offers higher robustness for the motion planner.
---
paper_title: Incrementally reducing dispersion by increasing Voronoi bias in RRTs

paper_content:

We discuss theoretical and practical issues related to using Rapidly-Exploring Random Trees (RRTs) to incrementally reduce dispersion in the configuration space. The original RRT planners use randomization to create Voronoi bias, which causes the search trees to rapidly explore the state space. We introduce RRT-like planners based on exact Voronoi diagram computation, as well as sampling-based algorithms which approximate their behavior. We give experimental results illustrating how the new algorithms explore the configuration space and how they compare with existing RRT algorithms. Initial results show that our algorithms are advantageous compared to existing RRTs, especially with respect to the number of collision checks and nodes in the search tree.
---
paper_title: Exponential Backoff-Sampling RRT for Smart Carpet

paper_content:

With the developing of sensor technology, smart materials and devices get increasing attention. Unlike desktop computing, smart devices typically have limited computing power and often need to react in real-time. So it’s difficult to directly apply complex algorithms on it due to the restriction in computational capability. Planning algorithm is one of these complex algorithms. In this paper, we proposed a new planning algorithm based on Rapid-exploring Random Trees (RRTs), which are currently widely used in robotics. In this paper, firstly we introduced the RRT algorithm and its analysis. Secondly, based on the analysis, we proposed an improved algorithm - Exponential Backoff sampling Rapid-exploring Random Tree (EB_RRT). The main idea in EB_RRT is to estimate the most efficacious sampling area to avoid useless sampling. In our experiments, we constructed a map with randomly placed obstacles. In the map, EB_RRT and several currently best algorithms were compared through solving a path planning problem. The results showed that our method makes an order of magnitude improvement than the existing ones and the low time consuming characteristic makes it a promising technology for smart devices.
---
paper_title: Sampling heuristics for optimal motion planning in high dimensions

paper_content:

We present a sampling-based motion planner that improves the performance of the probabilistically optimal RRT* planning algorithm. Experiments demonstrate that our planner finds a fast initial path and decreases the cost of this path iteratively. We identify and address the limitations of RRT* in high-dimensional configuration spaces. We introduce a sampling bias to facilitate and accelerate cost decrease in these spaces and a simple node-rejection criteria to increase efficiency. Finally, we incorporate an existing bi-directional approach to search which decreases the time to find an initial path. We analyze our planner on a simple 2D navigation problem in detail to show its properties and test it on a difficult 7D manipulation problem to show its effectiveness. Our results consistently demonstrate improved performance over RRT*.
---
paper_title: The Maverick planner: An efficient hierarchical planner for autonomous vehicles in unstructured environments

paper_content:

Planning kinodynamically feasible trajectories for autonomous vehicles is computationally expensive, especially when planning over long distances in unstructured environments. This paper presents a hierarchical planner, called the Maverick planner, which can find such trajectories efficiently. It comprises two parts: a waypoint planner that uses a simplified vehicle model and an RRT∗ planner that respects full kinodynamic constraints. The waypoint planner quickly finds a directed graph of waypoints from start to goal, which is then used to bias sampling and speed up computation in RRT∗. The Maverick planner is capable of anytime planning and continuous replanning. It has been tested extensively in simulation and on real vehicles. When planning on a sensor-generated map of the SwRI test track it can find a feasible path over 0.5 km in under 16 ms, and refine that path to within 1% of the local optimum in 0.5 seconds.
---
paper_title: The cross-entropy method for continuous multi-extremal optimization

paper_content:

In recent years, the cross-entropy method has been successfully applied to a wide range of discrete optimization tasks. In this paper we consider the cross-entropy method in the context of continuous optimization. We demonstrate the effectiveness of the cross-entropy method for solving difficult continuous multi-extremal optimization problems, including those with non-linear constraints.
---
paper_title: Guided RRT: A greedy search strategy for kinodynamic motion planning

paper_content:

Sampling-based methods, such as Probabilistic Roadmap Method(PRM)[l], Rapidly-Exploring Random Tree(RRT)[2], have been proposed as promising solutions for kinodynamic problems. Nevertheless, it's still a challenge for practical application especially for complex systems. In particular, most of the forward propagation is fruitless, which lead to heavy computation and be time-consuming. This paper presents a greedy kinodynamic motion planner: Guided RRT. The main characteristics are that the environments are explored by Geometric trees previously and nodes near the geometric feasible path enjoy more preference. Instead of exploring the environments uniformly, the new approach expands towards the goal greedily along a series of waypoints, with probabilistically completeness. And to guarantee the effective of the greed, a new distance metric based on Euclidean metric are proposed by considering both the current position and the following position with zero-input. We compare our technique with standard RRT and show that it achieves favorable performance when planning under kinodynamic constraints.
---
paper_title: Cross-entropy motion planning

paper_content:

This paper is concerned with motion planning for non-linear robotic systems operating in constrained environments. A method for computing high-quality trajectories is proposed building upon recent developments in sampling-based motion planning and stochastic optimization. The idea is to equip sampling-based methods with a probabilistic model that serves as a sampling distribution and to incrementally update the model during planning using data collected by the algorithm. At the core of the approach lies the cross-entropy method for the estimation of rare-event probabilities. The cross-entropy method is combined with recent optimal motion planning methods such as the rapidly exploring random trees (RRT*) in order to handle complex environments. The main goal is to provide a framework for consistent adaptive sampling that correlates the spatial structure of trajectories and their computed costs in order to improve the performance of existing planning methods.
---
paper_title: Interactive motion planning for assembly tasks

paper_content:

This paper presents an application of a motion planning algorithm to interactive systems. The proposed approach aims at improving the guidance of an operator during an assembling/dis-assembling task in a virtual environment with the help of an automatic path planning algorithm in PLM operations (PLM stands for Product Lifecycle Management, which is the process of managing the lifecycle of a product, from conception to service). Existing works use a two-step decomposition which limits the interaction between the user and the ongoing process. We propose a modification of a classic motion planning method, the Rapidly-exploring Random Tree to build an Interactive-RRT. This method is based on exchanging forces between the algorithm and the user, and on data gathering (labels) from the virtual scene. Examples are shown to illustrate the Interactive motion planning system.
---
paper_title: Informed RRT* towards optimality by reducing size of hyperellipsoid

paper_content:

Wrapping-based informed RRT* is a modified version of informed RRT*. Informed RRT* formulates an n-dimensional hyperellipsoid from which it generates new sample nodes. This has a dramatically increased chance of sampling nodes that will improve the current best solution compared to conventional RRT*. However, due to explorative and randomized behaviors of RRT*, the size of the hyperellipsoid will unlikely be small enough to call it effective. To solve this matter, wrapping-based informed RRT* proposed in this paper combines a size-diminishing procedure called ‘wrapping process’ with informed RRT*. The proposed planner can advance from the first solution acquired by the planner to the improved, feasible solution which can drastically reduce the size of the hyperellipsoid. Therefore, the required time consumption in order to acquire the globally optimal solution is reduced dramatically. The algorithm was tested in various environments with different numbers of joint variables and showed much better performance than the existing planners. Furthermore, the wrapping process proved to be a comparably insignificant computational burden regardless of the number of dimensions of the configuration space.
---
paper_title: Informed RRT*: Optimal Sampling-based Path Planning Focused via Direct Sampling of an Admissible Ellipsoidal Heuristic

paper_content:

Rapidly-exploring random trees (RRTs) are pop- ular in motion planning because they find solutions efficiently to single-query problems. Optimal RRTs (RRT*s) extend RRTs to the problem of finding the optimal solution, but in doing so asymptotically find the optimal path from the initial state to every state in the planning domain. This behaviour is not only inefficient but also inconsistent with their single-query nature. For problems seeking to minimize path length, the subset of states that can improve a solution can be described by a prolate hyperspheroid. We show that unless this subset is sam- pled directly, the probability of improving a solution becomes arbitrarily small in large worlds or high state dimensions. In this paper, we present an exact method to focus the search by directly sampling this subset. The advantages of the presented sampling technique are demonstrated with a new algorithm, Informed RRT*. This method retains the same probabilistic guarantees on complete- ness and optimality as RRT* while improving the convergence rate and final solution quality. We present the algorithm as a simple modification to RRT* that could be further extended by more advanced path-planning algorithms. We show exper- imentally that it outperforms RRT* in rate of convergence, final solution cost, and ability to find difficult passages while demonstrating less dependence on the state dimension and range of the planning problem.
---
paper_title: Batch Informed Trees (BIT*): Sampling-based Optimal Planning via the Heuristically Guided Search of Implicit Random Geometric Graphs

paper_content:

In this paper, we present Batch Informed Trees (BIT*), a planning algorithm based on unifying graph- and sampling-based planning techniques. By recognizing that a set of samples describes an implicit random geometric graph (RGG), we are able to combine the efficient ordered nature of graph-based techniques, such as A*, with the anytime scalability of sampling-based algorithms, such as Rapidly-exploring Random Trees (RRT).
---
paper_title: Self-learning RRT* Algorithm for Mobile Robot Motion Planning in Complex Environments

paper_content:

RRT* is a practical and efficient incremental sampling-based motion planning algorithm. However, its searching ability is quite inefficient in some cases, due to relying on uniform random sampling like other RRT-based algorithms without taking the environment information and prior knowledge into account, which particularly leads to many sampling failures or generation of useless nodes in complex environments. In this paper, we propose an extension of RRT* based on a self-learning strategy and a hybrid-biased sampling scheme to improve the planning efficiency. By taking advantage of the prior knowledge accumulation and cost estimation, the searching tree has higher probability and success rate to extend in difficult areas. We also demonstrate the performance of our algorithm by building some simulation environments for our mobile robot and conclude with the results compared with RRT*.
---
paper_title: Learning high-dimensional Mixture Models for fast collision detection in Rapidly-Exploring Random Trees

paper_content:

This paper presents a new approach for fast collision detection in high dimensional configuration spaces for Rapidly-exploring Random Trees (RRT) motion planning. The proposed method is based upon Gaussian Mixture Models (GMM) that are learned using an incremental Expectation Maximization clustering algorithm trained online using exemplars provided by a slow, conventional kinematic-based collision detection routine. The number of collision checks needed can be drastically reduced using a biased random sampling from the learned GMM distribution, and the learned models are continually refined and improved as the RRT planning algorithm proceeds. Our proposed method is demonstrated on several example applications and experimental results show marked improvement in computational efficiency over previous approaches.
---
paper_title: Use of relaxation methods in sampling-based algorithms for optimal motion planning

paper_content:

Several variants of incremental sampling-based algorithms have been recently proposed in order to optimally solve motion planning problems. Popular examples include the RRT* and the PRM* algorithms. These algorithms are asymptotically optimal and thus provide high quality solutions. However, the convergence rate to the optimal solution may still be slow. Borrowing from ideas used in the well-known LPA* algorithm, in this paper we present a new incremental sampling-based motion planning algorithm based on Rapidly-exploring Random Graphs (RRG), denoted by RRT# (RRT “sharp”), which also guarantees asymptotic optimality, but, in addition, it also ensures that the constructed spanning tree rooted at the initial state contains lowest-cost path information for vertices which have the potential to be part of the optimal solution. This implies that the best possible solution is readily computed if there are some vertices in the current graph that are already in the goal region.
---
paper_title: Adaptive sample bias for rapidly-exploring random trees with applications to test generation

paper_content:

We are developing a randomized approach to test generation for hybrid systems, and control systems in general, inspired by the rapidly-exploring random trees (RRTs) technique from robotic motion planning which has proved successful in solving high dimensional nonlinear problems. The approach represents an automated analysis alternative for systems where computing the reachable set is intractable. The standard RRTs method creates a tree in the state space by uniformly generating random sampling point and trying to find inputs which connect them. In this paper we propose a novel adaptive sampling strategy. We initially bias the distribution so that states near the "unsafe" set are selected. We continually monitor the growth of the tree. As the growth rate of the tree declines we adjust the sampling distribution to be less biased. This adaptive search strategy varies bias between "greedy" and global, often finding test trajectories more quickly than the traditional algorithm.
---
paper_title: Planning with ants: Efficient path planning with rapidly exploring random trees and ant colony optimization

paper_content:

Rapidly exploring random trees (RRTs) have been proven to be efficient for planning in environments populated with obstacles. These methods perform a uniform sampling of the state space, which is needed to guarantee the algorithm’s completeness but does not necessarily lead to the most efficient solution. In previous works it has been shown that the use of heuristics to modify the sampling strategy could incur an improvement in the algorithm performance. However, these heuristics only apply to solve the shortest path-planning problem. Here we propose a framework that allows us to incorporate arbitrary heuristics to modify the sampling strategy according to the user requirements. This framework is based on ‘learning from experience’. Specifically, we introduce a utility function that takes the contribution of the samples to the tree construction into account; sampling at locations of increased utility then becomes more frequent. The idea is realized by introducing an ant colony optimization concept in the RRT/RRT* algorithm and defining a novel utility function that permits trading off exploitation versus exploration of the state space. We also extend the algorithm to allow an anytime implementation. The scheme is validated with three scenarios: one populated with multiple rectangular obstacles, one consisting of a single narrow passage and a maze-like environment. We evaluate its performance in terms of the cost and time to find the first path, and in terms of the evolution of the path quality with the number of iterations. It is shown that the proposed algorithm greatly outperforms state-of-the-art RRT and RRT* algorithms.
---
paper_title: An rrt-based algorithm for testing and validating multi-robot controllers

paper_content:

Abstract : We address the problem of testing complex reactive control systems and validating the effectiveness of multi-agent controllers. Testing and validation involve searching for conditions that lead to system failure by exploring all adversarial inputs and disturbances for errant trajectories. This problem of testing is related to motion planning, with one main difference. Unlike motion planning problems, systems are typically not controllable with respect to disturbances or adversarial inputs and therefore, the reachable set of states is a small subset of the entire state space. In both cases however, there is a goal or specification set consisting of a set of points in state space that is of interest, either for demonstrating failure or for validation. In this paper we consider the application of the Rapidly exploring Random Tree algorithm to the testing and validation problem. Because of the differences between testing and motion planning, we propose three modifications to the original RRT algorithm. First, we introduce a new distance function which incorporates information about the system's dynamics to select nodes for extension. Second, we introduce a weighting to penalize nodes which are repeatedly selected but fail to extend. Third we propose a scheme for adaptively modifying the sampling probability distribution based on tree growth. We demonstrate the application of the algorithm via three simple and one large scale example and provide computational statistics. Our algorithms are applicable beyond the testing problem to motion planning for systems that are not small time locally controllable.
---
paper_title: Generalizing Informed Sampling for Asymptotically-Optimal Sampling-Based Kinodynamic Planning via Markov Chain Monte Carlo

paper_content:

Asymptotically-optimal motion planners such as RRT* have been shown to incrementally approximate the shortest path between start and goal states. Once an initial solution is found, their performance can be dramatically improved by restricting subsequent samples to regions of the state space that can potentially improve the current solution. When the motion planning problem lies in a Euclidean space, this region $X_{inf}$, called the informed set, can be sampled directly. However, when planning with differential constraints in non-Euclidean state spaces, no analytic solutions exists to sampling $X_{inf}$ directly. State-of-the-art approaches to sampling $X_{inf}$ in such domains such as Hierarchical Rejection Sampling (HRS) may still be slow in high-dimensional state space. This may cause the planning algorithm to spend most of its time trying to produces samples in $X_{inf}$ rather than explore it. In this paper, we suggest an alternative approach to produce samples in the informed set $X_{inf}$ for a wide range of settings. Our main insight is to recast this problem as one of sampling uniformly within the sub-level-set of an implicit non-convex function. This recasting enables us to apply Monte Carlo sampling methods, used very effectively in the Machine Learning and Optimization communities, to solve our problem. We show for a wide range of scenarios that using our sampler can accelerate the convergence rate to high-quality solutions in high-dimensional problems.
---
paper_title: A revised Gaussian distribution sampling scheme based on RRT* algorithms in robot motion planning

paper_content:

This paper introduces the basic Rapidly-Exploring Random Tree (RRT) and its basic modification Rapidly-Exploring Random Tree star (RRT*), which is not only the extension of RRT, but also a widely applied algorithm because of the properties of asymptotically optimal path regardless of any obstacles, whereas the limitation to achieve optimal path has a slow convergence rate. As a result, it costs too much memory and time due to a large number of iterations, so we propose a method that should change the sampling scheme from random distribution sampling to Gaussian distribution sampling to overcome this limitation. In order to apply the improved algorithm in robot arms or manipulators motion planning, we extend the RRT* to simulate in higher dimensional spaces, the planner is implemented in 3D workspace. Finally we also revise the Gaussian distribution to suit the practical environment.
---
paper_title: Fast approximation to gaussian obstacle sampling for randomized motion planning

paper_content:

Abstract We propose a new optimization of randomized motion planning via a local directed strategy. The basic motion planning problem is to find a collision free trajectory for a moving object (rigid, articulated or deformable) in a static or dynamic environment. We propose an improvement of the Rapidly-exploring Random Tree (RRT) method in associating the concepts of visibility and Gaussian sampling. This improvement focuses on the random sampling and its localization in free spaces. The new Gaussian sampling is described by a set of geometrical primitives and permits to define the random sampling behavior in the entire free space. In this paper, we first consider the existing alternatives for random sampling. Then we propose our localized random sampling that refines the environmental possibilities such as free space evaluation according to the mover's dynamic constraints. The environmental possibilities are identified during the RRT development. The experiments and results validate that our method improve the mover's trajectory in static environments.
---
paper_title: Machine learning guided exploration for sampling-based motion planning algorithms

paper_content:

We propose a machine learning (ML)-inspired approach to estimate the relevant region of a motion planning problem during the exploration phase of sampling-based path-planners. The algorithm guides the exploration so that it draws more samples from the relevant region as the number of iterations increases. The approach works in two steps: first, it predicts if a given sample is collision-free (classification phase) without calling the collision-checker, and it then estimates if it is a promising sample, i.e., if it has the potential to improve the current best solution (regression phase), without solving the local steering problem. The proposed exploration strategy is integrated to the RRT# algorithm. Numerical simulations demonstrate the efficiency of the proposed approach.
---
paper_title: Incrementally reducing dispersion by increasing Voronoi bias in RRTs

paper_content:

We discuss theoretical and practical issues related to using Rapidly-Exploring Random Trees (RRTs) to incrementally reduce dispersion in the configuration space. The original RRT planners use randomization to create Voronoi bias, which causes the search trees to rapidly explore the state space. We introduce RRT-like planners based on exact Voronoi diagram computation, as well as sampling-based algorithms which approximate their behavior. We give experimental results illustrating how the new algorithms explore the configuration space and how they compare with existing RRT algorithms. Initial results show that our algorithms are advantageous compared to existing RRTs, especially with respect to the number of collision checks and nodes in the search tree.
---
paper_title: Fast approximation to gaussian obstacle sampling for randomized motion planning

paper_content:

Abstract We propose a new optimization of randomized motion planning via a local directed strategy. The basic motion planning problem is to find a collision free trajectory for a moving object (rigid, articulated or deformable) in a static or dynamic environment. We propose an improvement of the Rapidly-exploring Random Tree (RRT) method in associating the concepts of visibility and Gaussian sampling. This improvement focuses on the random sampling and its localization in free spaces. The new Gaussian sampling is described by a set of geometrical primitives and permits to define the random sampling behavior in the entire free space. In this paper, we first consider the existing alternatives for random sampling. Then we propose our localized random sampling that refines the environmental possibilities such as free space evaluation according to the mover's dynamic constraints. The environmental possibilities are identified during the RRT development. The experiments and results validate that our method improve the mover's trajectory in static environments.
---

Title: Systematic Literature Review of Sampling Process in Rapidly-Exploring Random Trees

Section 1: INTRODUCTION
Description 1: Introduce the topic of path planning and the role of the RRT algorithm in various applications, emphasizing the importance of sampling processes.

Section 2: PATH PLANNING ALGORITHMS
Description 2: Discuss different path planning algorithms, comparing classical and sampling-based methods, and explain their computational models and applications.

Section 3: RAPIDLY-EXPLORING RANDOM TREE (RRT)
Description 3: Describe the RRT algorithm in detail, including its structure, operation, and various extensions and improvements.

Section 4: ROLE OF SAMPLING IN RRT
Description 4: Explain the types of sampling in RRT (uniform and non-uniform), their characteristics, and how they affect the performance of the algorithm.

Section 5: SYSTEMATIC LITERATURE REVIEW PROTOCOL
Description 5: Outline the protocol used for conducting the systematic literature review, including the scope, research questions, search strings, selection criteria, and data extraction process.

Section 6: DEVELOPMENT OF THE SYSTEMATIC LITERATURE REVIEW
Description 6: Describe the phases of the SLR process, including the scope outline, filtering of primary studies, and data extraction.

Section 7: RESULTS OF THE SYSTEMATIC LITERATURE REVIEW
Description 7: Present the results and findings of the SLR, categorized into different strategies of non-uniform/informed sampling, detailing the primary studies and their contributions.

Section 8: CONCLUSION
Description 8: Summarize the key findings of the review, discuss their implications for future research and applications, and suggest potential areas for further study.