A Learning-based Multi-RRT Approach for Robot Path Planning in Narrow Passages

As an important class of sampling-based path planning methods, the Rapidly-exploring Random Trees (RRT) algorithm has been widely studied and applied in the literature. In RRT, how to select a tree to extend or connect is a critical factor, which will greatly influence the efficiency of path planning. In this paper, a novel learning-based multi-RRTs (LM-RRT) approach is proposed for robot path planning in narrow passages. The LM-RRT approach models the tree selection process as a multi-armed bandit problem and uses a reinforcement learning algorithm that learns action values and selects actions with an improved ε-greedy strategy (ε _t -greedy). Compared with previous RRT algorithms, LM-RRT can not only enhance the local space exploration ability of each tree, but also guarantee the efficiency of global path planning. The probabilistic completeness and combinatory optimality of LM-RRT are proved based on the geometric characteristics of the configuration space. Simulation and experimental results show the effectiveness of the proposed LM-RRT approach in single-query path planning problems with narrow passages.     

<Emphasis Type="Italic">κ</Emphasis>-<Emphasis Type="Italic">PMP</Emphasis>: Enhancing Physics-based Motion Planners with Knowledge-Based Reasoning

Physics-based motion planning is a challenging task, since it requires the computation of the robot motions while allowing possible interactions with (some of) the obstacles in the environment. Kinodynamic motion planners equipped with a dynamic engine acting as state propagator are usually used for that purpose. The difficulties arise in the setting of the adequate forces for the interactions and because these interactions may change the pose of the manipulatable obstacles, thus either facilitating or preventing the finding of a solution path. The use of knowledge can alleviate the stated difficulties. This paper proposes the use of an enhanced state propagator composed of a dynamic engine and a low-level geometric reasoning process that is used to determine how to interact with the objects, i.e. from where and with which forces. The proposal, called κ-PMP can be used with any kinodynamic planner, thus giving rise to e.g. κ-RRT. The approach also includes a preprocessing step that infers from a semantic abstract knowledge described in terms of an ontology the manipulation knowledge required by the reasoning process. The proposed approach has been validated with several examples involving an holonomic mobile robot, a robot with differential constraints and a serial manipulator, and benchmarked using several state-of-the art kinodynamic planners. The results showed a significant difference in the power consumption with respect to simple physics-based planning, an improvement in the success rate and in the quality of the solution paths.     

Grafting: A Path Replanning Technique for Rapidly-Exploring Random Trees in Dynamic Environments

The rapidly-exploring random trees (RRT) is a sampling-based path planner which utilizes simultaneously kinematics and dynamics of a robot. However, since the RRT has produced a robot path without taking the existence of dynamic obstacles into consideration, RRT-based navigation has the risk of a collision with dynamic obstacles. We proposed a path replanning technique for the RRT applied to robot navigation in dynamic environments, which is named grafting. The proposed technique replans a safe and efficient path in real time instead of the original path which may cause a collision with dynamic obstacles. Moreover, the replanned path can be easily merged into the original RRT path because the grafting technique preserves the property of the RRT. The grafting technique was tested by simulations in various dynamic environments, which revealed that the grafting technique was capable of replanning a safe and efficient path for RRT-based navigation in real time.     

Planning Robot Navigation among Movable Obstacles (NAMO) through a Recursive Approach

This paper addresses the NP-complete problem of Navigation Among Movable Obstacles (NAMO) in which a robot is required to find a collision-free path toward a goal through manipulating and transferring some movable objects on its way. The robot’s main goal is to optimize a performance criterion such as runtime, length of transit or transfer paths, number of manipulated obstacles, total number of displacements of all objects, etc. We have designed a recursive algorithm capable of solving various NAMO problems, ranging from linear monotone to nonlinear non-monotone, and with convex or concave polygonal obstacles. Through the adopted approach, the original problem is decomposed into recursively-solved subproblems, in each of which only one movable object is manipulated. In each call of the algorithm, first a Visibility Graph determines a path from the robot’s current configuration to an intermediate goal configuration, and then a tentative final configuration for the last object intercepting the path is calculated using the Penetration Depth concept. It is assumed that the objects can be pulled or pushed, but not rotated, in a continuous space, and under such assumptions the method is complete and locally optimal for convex objects, with a worst-case time complexity of O(n⁴3^m) in which m is the number of movable objects and n is the number of all vertices on them. Several computational experiments showed that compared to the existing methods in the literature, the proposed recursive method achieved equal or smaller number of transferred obstacles or the total number of displacements of all objects in majority of the test problems.     

Adaptive Behaviors in Autonomous Navigation with Collision Avoidance and Bounded Velocity of an Omnidirectional Mobile Robot

Integration of Control Theory and Genetic Programming paradigm toward development a family of controllers is addressed in this paper. These controllers are applied for autonomous navigation with collision avoidance and bounded velocity of an omnidirectional mobile robot. We introduce the concepts of natural and adaptive behaviors to relate each control objective with a desired behavior for the mobile robot. Natural behaviors lead the system to fulfill a task inherently. In this work, the motion of the mobile robot to achieve desired position, ensured by applying a Control-Theory-based controller, defines the natural behavior. The adaptive behavior, learned through Genetic-Programming, fits the robot motion in order to avoid collision with an obstacle while fulfilling velocity constraints. Hence, the behavior of the mobile robot is the addition of the natural and the adaptive behaviors. Our proposed methodology achieves the discovery of 9402 behaviors without collisions where asymptotic convergence to desired goal position is demonstrated by Lyapunov stability theory. Effectiveness of proposed framework is illustrated through a comparison between experiments and numerical simulations for a real mobile robot.     

Multi-agent Rapidly-exploring Pseudo-random Tree

Real-time motion planning and control for groups of heterogeneous and under-actuated robots subject to disturbances and uncertainties in cluttered constrained environments is the key problem addressed in this paper. Here we present the Multi-agent Rapidly-exploring Pseudo-random Tree (MRPT), a novel technique based on a classical Probabilistic Road Map (PRM) algorithm for application in robot team cooperation. Our main contribution lies in the proposal of an extension of a probabilistic approach to be used as a deterministic planner in distributed complex multi-agent systems, keeping the main advantages of PRM strategies like simplicity, fast convergence, and probabilistic completeness. Our methodology is fully distributed, addressing missions with multi-robot teams represented by high nonlinear models and a great number of Degrees of Freedom (DoFs), endowing each agent with the ability of coordinating its own movement with other agents while avoiding collisions with obstacles. The inference of the entire team’s behavior at each time instant by each individual agent is the main improvement of our method. This scheme, which is behavioral in nature, also makes the system less susceptible to failures due to intensive traffic communication among robots. We evaluate the time complexity of our method and show its applicability in planning and executing search and rescue missions for a group of robots in S E3 outdoor scenarios and present both simulated and real-world results.     

Continuous visible nearest neighbor query processing in spatial databases

In this paper, we identify and solve a new type of spatial queries, called continuous visible nearest neighbor (CVNN) search. Given a data set P, an obstacle set O, and a query line segment q in a two-dimensional space, a CVNN query returns a set of \({\langle p, R\rangle}\) tuples such that \({p \in P}\) is the nearest neighbor to every point r along the interval \({R \subseteq q}\) as well as p is visible to r. Note that p may be NULL, meaning that all points in P are invisible to all points in R due to the obstruction of some obstacles in O. In contrast to existing continuous nearest neighbor query, CVNN retrieval considers the impact of obstacles on visibility between objects, which is ignored by most of spatial queries. We formulate the problem, analyze its unique characteristics, and develop efficient algorithms for exact CVNN query processing. Our methods (1) utilize conventional data-partitioning indices (e.g., R-trees) on both P and O, (2) tackle the CVNN search by performing a single query for the entire query line segment, and (3) only access the data points and obstacles relevant to the final query result by employing a suite of effective pruning heuristics. In addition, several interesting variations of CVNN queries have been introduced, and they can be supported by our techniques, which further demonstrates the flexibility of the proposed algorithms. A comprehensive experimental evaluation using both real and synthetic data sets has been conducted to verify the effectiveness of our proposed pruning heuristics and the performance of our proposed algorithms.     

Efficient distance-based representative skyline computation in 2D space

Representative skyline computation is a fundamental issue in database area, which has attracted much attention in recent years. A notable definition of representative skyline is the distance-based representative skyline (DBRS). Given an integer k, a DBRS includes k representative skyline points that aims at minimizing the maximal distance between a non-representative skyline point and its nearest representative. In the 2D space, the state-of-the-art algorithm to compute the DBRS is based on dynamic programming (DP) which takes O(k m ²) time complexity, where m is the number of skyline points. Clearly, such a DP-based algorithm cannot be used for handling large scale datasets due to the quadratic time cost. To overcome this problem, in this paper, we propose a new approximate algorithm called ARS, and a new exact algorithm named PSRS, based on a carefully-designed parametric search technique. We show that the ARS algorithm can guarantee a solution that is at most ?? larger than the optimal solution. The proposed ARS and PSRS algorithms run in O(klog2mlog(T/??)) and O(k ² log3m) time respectively, where T is no more than the maximal distance between any two skyline points. We also propose an improved exact algorithm, called PSRS+, based on an effective lower and upper bounding technique. We conduct extensive experimental studies over both synthetic and real-world datasets, and the results demonstrate the efficiency and effectiveness of the proposed algorithms.     

Set-point Control of Mobile Robot with Obstacle Detection and Avoidance Using Navigation Function - Experimental Verification

This paper presents the results of an experimental verification of mobile robot control algorithm including obstacle detection and avoidance. The controller is based on the navigation potential function that was proposed in work (Urakubo, Nonlinear Dyn. 81(3), 1475–1487 2015). Conducted experiments considered the task of reaching and stabilization of robot in point. The navigation potential agregates information of robot position and orientation but also the repelling potentials of obstacles. The obstacle detection is performed solely with the use of laser scanner. The experiments show that the method can easily handle environments with one or two obstacles even if they instantly hide or show-up due to the scanner range limits. The experiments also indicate that the utilized control method has a good potential for being used in parallel parking task.     

An Improved Extended Active Observer for Adaptive Control of A <Emphasis Type="Italic">n</Emphasis><Emphasis Type="Italic">−</Emphasis>DOF Robot Manipulator

A novel algorithm for simultaneous force estimation and friction compensation of constrained motion of robot manipulators is presented. This represents an extension of the improved extended active observer (IEAOB) algorithm reported earlier and proposes a higher order IEAOB or N?th order IEAOB (IEAOB ?N) for a n?DOF robot manipulator. Central to this observer is the use of extra system states modeled as a Gauss-Markov (GM) formulation to estimate the force and disturbances including robot inertial parameters and friction. The stability of IEAOB ?N is verified through stability analysis. The IEAOB-1 is validated by applying it to a Phantom Omni haptic device against a Nicosia observer, disturbance observer (DOB)/reaction torque observer (RTOB), and nonlinear disturbance observer (NDO), respectively. The results show that the proposed IEAOB-1 is superior to the compared observers in terms of force estimation. Then, the performance of the IEAOB ? N is experimentally studied and compared to the IEAOB-1. Results demonstrate that the IEAOB ? N has an improved capability in tracking nonlinear external forces.     

Ranking policies in discrete Markov decision processes

An optimal probabilistic-planning algorithm solves a problem, usually modeled by a Markov decision process, by finding an optimal policy. In this paper, we study the k best policies problem. The problem is to find the k best policies of a discrete Markov decision process. The k best policies, k?>?1, cannot be found directly using dynamic programming. Naïvely, finding the k-th best policy can be Turing reduced to the optimal planning problem, but the number of problems queried in the naïve algorithm is exponential in k. We show empirically that solving k best policies problem by using this reduction requires unreasonable amounts of time even when k?=?3. We then provide two new algorithms. The first is a complete algorithm, based on our theoretical contribution that the k-th best policy differs from the i-th policy, for some i?k, on exactly one state. The second is an approximate algorithm that skips many less useful policies. We show that both algorithms have good scalability. We also show that the approximate algorithms runs much faster and finds interesting, high-quality policies.     

Chain sequences with ordered enclosing

To enhance the efficiency of numerical control machines for cutting of sheet material, a method of searching for the cutter trajectory as a path with ordered enclosing in the flat graph G = (V, E) corresponding to the cutting design is proposed. It is shown that this path can be represented as a sequence of no more than n/2 + 1 chains with ordered enclosing, where n is the number of odd-order vertices in G. An algorithm for finding the sought sequence of chains, with a complexity of O(|E|) is developed.     

Cost-Based Target Selection Techniques Towards Full Space Exploration and Coverage for USAR Applications in a Priori Unknown Environments

Full coverage and exploration of an environment is essential in robot rescue operations where victim identification is required. Three methods of target selection towards full exploration and coverage of an unknown space oriented for Urban Search and Rescue (USAR) applications have been developed. These are the Selection of the closest topological node, the Selection of the minimum cost topological node and the Selection of the minimum cost sub-graph. All methods employ a topological graph extracted from the Generalized Voronoi Diagram (GVD), in order to select the next best target during exploration. The first method utilizes a distance metric for determining the next best target whereas the Selection of the minimum cost topological node method assigns four different weights on the graph’s nodes, based on certain environmental attributes. The Selection of the minimum cost sub-graph uses a similar technique, but instead of single nodes, sets of graph nodes are examined. In addition, a modification of A* algorithm for biased path creation towards uncovered areas, aiming at a faster spatial coverage, is introduced. The proposed methods’ performance is verified by experiments conducted in two heterogeneous simulated environments. Finally, the results are compared with two common exploration methods.     

K-Order Surrounding Roadmaps Path Planner for Robot Path Planning

Probabilistic roadmaps are commonly used in robot path planning. Most sampling-based path planners often produce poor-quality roadmaps as they focus on improving the speed of constructing roadmaps without paying much attention to the quality. Poor-quality roadmaps can cause problems such as poor-quality paths, time-consuming path searching and failures in the searching. This paper presents a K-order surrounding roadmap (KSR) path planner which constructs a roadmap in an incremental manner. The planner creates a tree while answering a query, selects the part of the tree according to quality measures and adds the part to an existing roadmap which is obtained in the same way when answering the previous queries. The KSR path planner is able to construct high-quality roadmaps in terms of good coverage, high connectivity, provision of alternative paths and small size. Comparison between the KSR path planner and Reconfigurable Random Forest (RRF), an existing incremental path planner, as well as traditional probabilistic roadmap (PRM) path planner shows that the roadmaps constructed using the KSR path planner have higher quality that those that are built by the other planners.     

Automatic hair extraction from 2D images

Automatic hair extraction from a given 2D image has been a challenging problem for a long time, especially when complex backgrounds and a wide variety of hairstyles are involved. This paper has made its contribution in the following three aspects. First, it proposes a novel framework that successfully combines the techniques of face detection, outlier-aware initial stroke placement and matting to extract the desired hair region from an input image. Second, it introduces an alpha space to facilitate the choice of matting parameters. Third, it defines a new comparison metric that is well suited for the alpha matte comparison. Our results show that, compared with the manually drawn trimaps for hair extraction, the proposed automatic algorithm can achieve about 86.2 % extraction accuracy.     

On the Advice Complexity of the k-server Problem Under Sparse Metrics

We consider the k-Server problem under the advice model of computation when the underlying metric space is sparse. On one side, we introduce Θ(1)-competitive algorithms for a wide range of sparse graphs. These algorithms require advice of (almost) linear size. We show that for graphs of size N and treewidth α, there is an online algorithm that receives O (n(log α + log log N))^* bits of advice and optimally serves any sequence of length n. We also prove that if a graph admits a system of μ collective tree (q, r)-spanners, then there is a (q + r)-competitive algorithm which requires O (n(log μ + log log N)) bits of advice. Among other results, this gives a 3-competitive algorithm for planar graphs, when provided with O (n log log N) bits of advice. On the other side, we prove that advice of size Ω(n) is required to obtain a 1-competitive algorithm for sequences of length n even for the 2-server problem on a path metric of size N ≥ 3. Through another lower bound argument, we show that at least \(\frac {n}{2}(\log \alpha - 1.22)\) bits of advice is required to obtain an optimal solution for metric spaces of treewidth α, where 4 ≤ α < 2k.     

Improved Approximation Algorithm for k-level Uncapacitated Facility Location Problem (with Penalties)

We study the k-level uncapacitated facility location problem (k-level UFL) in which clients need to be connected with paths crossing open facilities of k types (levels). In this paper we first propose an approximation algorithm that for any constant k, in polynomial time, delivers solutions of cost at most α _k times OPT, where α _k is an increasing function of k, with \(\lim _{k\to \infty } \alpha _{k} = 3\). Our algorithm rounds a fractional solution to an extended LP formulation of the problem. The rounding builds upon the technique of iteratively rounding fractional solutions on trees (Garg, Konjevod, and Ravi SODA’98) originally used for the group Steiner tree problem. We improve the approximation ratio for k-level UFL for all k ≥ 3, in particular we obtain the ratio equal 2.02, 2.14, and 2.24 for k = 3,4, and 5.     

Attractor dynamics approach to formation control: theory and application

In this paper we show how non-linear attractor dynamics can be used as a framework to control teams of autonomous mobile robots that should navigate according to a predefined geometric formation. The environment does not need to be known a priori and may change over time. Implicit to the control architecture are some important features such as establishing and moving the formation, split and join of formations (when necessary to avoid obstacles). Formations are defined by a formation matrix. By manipulating this formation matrix it is also possible to switch formations at run time. Examples of simulation results and implementations with real robots (teams of Khepera robots and medium size mobile robots), demonstrate formation switch, static and dynamic obstacle avoidance and split and join formations without the need for any explicit coordination scheme. Robustness against environmental perturbations is intrinsically achieved because the behaviour of each robot is generated as a time series of asymptotically stable states, which contribute to the asymptotic stability of the overall control system.