An Optimized Probabilistic Roadmap Algorithm for Path Planning of Mobile Robots in Complex Environments with Narrow Channels

In this paper, we propose a new path planning algorithm based on the probabilistic roadmaps method (PRM), in order to effectively solve the autonomous path planning of mobile robots in complex environments with multiple narrow channels. The improved PRM algorithm mainly improves the density and distribution of sampling points in the narrow channel, through a combination of the learning process of the PRM algorithm and the APF algorithm. We also shortened the required time and path length by optimizing the query process. The first key technology to improve the PRM algorithm involves optimizing the number and distribution of free points and collision-free lines in the free workspace. To ensure full visibility of the narrow channel, we extend the obstacles through the diagonal distance of the mobile robot while ignoring the safety distance. Considering the safety distance during movement, we re-classify the all sampling points obtained by the quasi-random sampling principle into three categories: free points, obstacle points, and adjacent points. Next, we transform obstacle points into the free points of the narrow channel by combining the APF algorithm and the characteristics of the narrow channel, increasing the density of sampling points in the narrow space. Then, we include potential energy judgment into the construction process of collision-free lines shortening the required time and reduce collisions with obstacles. Optimizing the query process of the PRM algorithm is the second key technology. To reduce the required time in the query process, we adapt the bidirectional A* algorithm to query these local paths and obtain an effective path to the target point. We also combine the path pruning technology with the potential energy function to obtain a short path without collisions. Finally, the experimental results demonstrate that the new PRM path planning technology can improve the density of free points in narrow spaces and achieve an optimized, collision-free path in complex environments with multiple narrow channels.

Efficient Path Planning for a Microrobot Passing through Environments with Narrow Passages

This paper presents an efficient path-planning algorithm for microrobots attempting to pass through environments with narrow passages. Because of the extremely small size of a microrobot, it is suitable for work in this kind of environment. The rapidly exploring random tree (RRT) algorithm, which uses random sampling points, can quickly explore an entire environment and generate a sub-optimal path for a robot to pass through it; however, the RRT algorithm, when used to plan a path for a microrobot passing through an environment with narrow passages, has the problem of being easily limited to local solutions when it confronts with a narrow passage and is unable to find the final path through it. In light of this, the objectives of the considered path planning problem involve detecting the narrow passages, leading the path toward an approaching narrow passage, passing through a narrow passage, and extending the path search more efficiently. A methodology was proposed based on the bidirectional RRT in which image processing is used to mark narrow passages and their entrances and exits so that the bidirectional RRT can be quickly guided to them and combined with the deterministic algorithm to find paths through them. We designed the methodology such that RRT generates the sampling points for path growth. The multiple importance sampling technique is incorporated with bidirectional RRT, named MIS-BiRRT, to make the path grow faster toward the target point and narrow passages while avoiding obstacles. The proposed algorithm also considers multiple candidate paths simultaneously to expand the search range and then retain the best one as a part of the planning path. After validation from simulation, the proposed algorithm was found to generate efficient path planning results for microrobots to pass through narrow passages.

Motion Planning for Mobile Manipulators—A Systematic Review

One of the fundamental fields of research is motion planning. Mobile manipulators present a unique set of challenges for the planning algorithms, as they are usually kinematically redundant and dynamically complex owing to the different dynamic behavior of the mobile base and the manipulator. The purpose of this article is to systematically review the different planning algorithms specifically used for mobile manipulator motion planning. Depending on how the two subsystems are treated during planning, sampling-based, optimization-based, search-based, and other planning algorithms are grouped into two broad categories. Then, planning algorithms are dissected and discussed based on common components. The problem of dealing with the kinematic redundancy in calculating the goal configuration is also analyzed. While planning separately for the mobile base and the manipulator provides convenience, the results are sub-optimal. Coordinating between the mobile base and manipulator while utilizing their unique capabilities provides better solution paths. Based on the analysis, challenges faced by the current planning algorithms and future research directions are presented.

Towards Autonomous Robotic Assembly: Using Combined Visual and Tactile Sensing for Adaptive Task Execution

Robotic assembly tasks are typically implemented in static settings in which parts are kept at fixed locations by making use of part holders. Very few works deal with the problem of moving parts in industrial assembly applications. However, having autonomous robots that are able to execute assembly tasks in dynamic environments could lead to more flexible facilities with reduced implementation efforts for individual products. In this paper, we present a general approach towards autonomous robotic assembly that combines visual and intrinsic tactile sensing to continuously track parts within a single Bayesian framework. Based on this, it is possible to implement object-centric assembly skills that are guided by the estimated poses of the parts, including cases where occlusions block the vision system. In particular, we investigate the application of this approach for peg-in-hole assembly. A tilt-and-align strategy is implemented using a Cartesian impedance controller, and combined with an adaptive path executor. Experimental results with multiple part combinations are provided and analyzed in detail.

Multiple-Target Homotopic Quasi-Complete Path Planning Method for Mobile Robot Using a Piecewise Linear Approach

The ability to plan a multiple-target path that goes through places considered important is desirable for autonomous mobile robots that perform tasks in industrial environments. This characteristic is necessary for inspection robots that monitor the critical conditions of sectors in thermal, nuclear, and hydropower plants. This ability is also useful for applications such as service at home, victim rescue, museum guidance, land mine detection, and so forth. Multiple-target collision-free path planning is a topic that has not been very studied because of the complexity that it implies. Usually, this issue is left in second place because, commonly, it is solved by segmentation using the point-to-point strategy. Nevertheless, this approach exhibits a poor performance, in terms of path length, due to unnecessary turnings and redundant segments present in the found path. In this paper, a multiple-target method based on homotopy continuation capable to calculate a collision-free path in a single execution for complex environments is presented. This method exhibits a better performance, both in speed and efficiency, and robustness compared to the original Homotopic Path Planning Method (HPPM). Among the new schemes that improve their performance are the Double Spherical Tracking (DST), the dummy obstacle scheme, and a systematic criterion to a selection of repulsion parameter. The case studies show its effectiveness to find a solution path for office-like environments in just a few milliseconds, even if they have narrow corridors and hundreds of obstacles. Additionally, a comparison between the proposed method and sampling-based planning algorithms (SBP) with the best performance is presented. Furthermore, the results of case studies show that the proposed method exhibits a better performance than SBP algorithms for execution time, memory, and in some cases path length metrics. Finally, to validate the feasibility of the paths calculated by the proposed planner; two simulations using the pure-pursuit controlled and differential drive robot model contained in the Robotics System Toolbox of MATLAB are presented.

Collision-Free Path Planning Method for Robots Based on an Improved Rapidly-Exploring Random Tree Algorithm

Sampling-based methods are popular in the motion planning of robots, especially in high-dimensional spaces. Among the many such methods, the Rapidly-exploring Random Tree (RRT) algorithm has been widely used in multi-degree-of-freedom manipulators and has yielded good results. However, existing RRT planners have low exploration efficiency and slow convergence speed and have been unable to meet the requirements of the intelligence level in the Industry 4.0 mode. To solve these problems, a general autonomous path planning algorithm of Node Control (NC-RRT) is proposed in this paper based on the architecture of the RRT algorithm. Firstly, a method of gradually changing the sampling area is proposed to guide exploration, thereby effectively improving the search speed. In addition, the node control mechanism is introduced to constrain the extended nodes of the tree and thus reduce the extension of invalid nodes and extract boundary nodes (or near-boundary nodes). By changing the value of the node control factor, the random tree is prevented from falling into a so-called “local trap” phenomenon, and boundary nodes are selected as extended nodes. The proposed algorithm is simulated in different environments. Results reveal that the algorithm greatly reduces the invalid exploration in the configuration space and significantly improves planning efficiency. In addition, because this method can efficiently use boundary nodes, it has a stronger applicability to narrow environments compared with existing RRT algorithms and can effectively improve the success rate of exploration.

Collision-Free Path Planning and Delivery Sequence Optimization in Noncoplanar Radiation Therapy

Radiation therapy is among the top three cancer treatments in current medical services. The novel noncoplanar radiation therapy which claimed the best characteristics in almost all dosimetric properties encountered the challenges of the potential collision and the long time delivering. In this paper, we proposed a brand new scheme which uses a combined method of the collision avoidance path planning based on an improved probability roadmap method (PRM) and the delivery sequence optimization based on a modified genetic algorithm (GA) to solve the problems in noncoplanar radiation therapy. A uniform sampling strategy, an improved connection strategy, and an efficient local planner are introduced to optimize the roadmap result and accelerate the roadmap construction. The GA is improved by the elitist selection, the local search strategy, and the similar substitution strategy to achieve a better performance both in convergence rate and optimal solution. Experiments are carried out on the simulation platform with typical therapy system models. The results show that our proposed methods work well with the radiation therapy system in a compact working area. Collision is avoided and time consumption is reduced. We believe that our proposed algorithms could solve the problems in current radiation therapy and promote their clinic applications.

RimJump: Edge-based Shortest Path Planning for a 2D Map

Path planning under 2D map is a key issue in robot applications. However, most related algorithms rely on point-by-point traversal. This causes them usually cannot find the strict shortest path, and their time cost increases dramatically as the map scale increases. So we proposed RimJump to solve the above problem, and it is a new path planning method that generates the strict shortest path for a 2D map. RimJump selects points on the edge of barriers to form the strict shortest path. Simulation and experimentation prove that RimJump meets the expected requirements.

A Region-Specific Hybrid Sampling Method for Optimal Path Planning

Finding high quality paths within a limited time in configuration space is a challenging issue for path planning. Recently, an asymptotically optimal method called fast marching tree (FMT*) has been proposed. This method converges significantly faster than its state-of-the-art counterparts when addressing a wide range of problems. However, FMT* appears unable to solve the narrow passage problem in optimal path planning, since it is based on uniform sampling. Aiming at solving this problem, a novel region-based sampling method integrating global scenario information and local region information is proposed in this paper. First, global information related to configuration space is extracted from an initial sample set obtained via hybrid sampling. Then, local regions are constructed and local region information is captured to make intelligent decisions regarding regions that are difficult and need to be boosted. Finally, the initial sample set is sent to FMT* using a modified locally optimal one-step connection strategy in order to find an initial and feasible solution. If no solution is found and time permits, the guided hybrid sampling will be adopted in order to add more useful samples to the sample set until a solution is found or the time for doing so runs out. Simulation results for six benchmark scenarios validate that our method can achieve significantly better results than other state-of-the-art methods when applied in challenging scenarios with narrow passages.

Fast probabilistic collision checking for sampling-based motion planning using locality-sensitive hashing

We present a novel approach to perform fast probabilistic collision checking in high-dimensional configuration spaces to accelerate the performance of sampling-based motion planning. Our formulation stores the results of prior collision queries, and then uses such information to predict the collision probability for a new configuration sample. In particular, we perform an approximate k-NN ( k-nearest neighbor) search to find prior query samples that are closest to the new query configuration. The new query sample’s collision status is then estimated according to the collision checking results of these prior query samples, based on the fact that nearby configurations are likely to have the same collision status. We use locality-sensitive hashing techniques with sub-linear time complexity for approximate k-NN queries. We evaluate the benefit of our probabilistic collision checking approach by integrating it with a wide variety of sampling-based motion planners, including PRM (Probabilistic roadmaps), lazyPRM, RRT Rapidly exploring random trees, and RRT*. Our method can improve these planners in various manners, such as accelerating the local path validation, or computing an efficient order for the graph search on the roadmap. Experiments on a set of benchmarks demonstrate the performance of our method, and we observe up to 2x speedup in the performance of planners on rigid and articulated robots.

Path planning in distorted configuration space

An effective algorithm for path planning is introduced based on a novel concept, the distorted configuration space (DC-space), where all obstacles deform into dimensionless geometric objects. Path planning in this space can be conducted by simply connecting the starting position and ending position with a straight line. This linear path in the DC-space is then mapped back into a feasible in the original C-space. The advantage of this approach is that no trial-and-error or iteration is needed while a feasible path can be found directly if it exists. An algorithm with general formulas is derived. Examples in 2D and 3D are provided to validate this concept and algorithm.

Path Planning with a Lazy Significant Edge Algorithm (LSEA)

Probabilistic methods have been proven to be effective for robotic path planning in a geometrically complex environment. In this paper, we propose a novel approach, which utilizes a specialized roadmap expansion phase, to improve lazy probabilistic path planning. This expansion phase analyses roadmap connectivity information to bias sampling towards objects in the workspace that have not yet been navigated by the robot. A new method to reduce the number of samples required to navigate narrow passages is also proposed and tested. Experimental results show that the new algorithm is more efficient than the traditional path planning methodologies. It was able to generate solutions for a variety of path planning problems faster, using fewer samples to arrive at a valid solution.