Category Archives: Robot Motion Planning

A mathematical study of controllers that produce paths with beautfiul shapes to reach a target point by a unicycle vehicle

April 26, 2018 07:25 ,

T. Tripathy and A. Sinha, Unicycle With Only Range Input: An Array of Patterns, IEEE Transactions on Automatic Control, vol. 63, no. 5, pp. 1300-1312, DOI: 10.1109/TAC.2017.2736940.

The objective of this paper is to generate planar patterns using an autonomous agent modeled as a unicycle. The patterns are generated about a stationary point referred to as the target. To achieve the same, the paper proposes a family of control inputs that are continuous functions of range, which is the distance between the unicycle and the target. The paper studies in detail a characterization of the resulting trajectories, which are a plethora of patterns of parametric curves (circles, spirals, epicyclic curves like hypotrochoids) and more. These appealing patterns find applications in exploration, coverage, land mine detection, etc., where the target represents any point of interest like a landmark or a beacon. The paper also investigates the necessary conditions on the control laws in order to generate patterns of desired shapes and bounds. Furthermore, to generate desired patterns with arbitrary initial conditions, a switching strategy is proposed which is illustrated using an algorithm. The paper presents a series of simulations of appealing patterns generated using the proposed control laws.

Posted in: Control Engineering, Robot motion planning

A novel algorithm for coverage path planning with very strong guarantees

April 19, 2018 07:38 ,

J. Song and S. Gupta, $varepsilon ^{star }$: An Online Coverage Path Planning Algorithm, IEEE Transactions on Robotics, vol. 34, no. 2, pp. 526-533, DOI: 10.1109/TRO.2017.2780259.

This paper presents an algorithm called ε*, for online coverage path planning of unknown environment. The algorithm is built upon the concept of an Exploratory Turing Machine (ETM), which acts as a supervisor to the autonomous vehicle to guide it with adaptive navigation commands. The ETM generates a coverage path online using Multiscale Adaptive Potential Surfaces (MAPS), which are hierarchically structured and dynamically updated based on sensor information. The ε*-algorithm is computationally efficient, guarantees complete coverage, and does not suffer from the local extrema problem. Its performance is validated by 1) high-fidelity simulations on Player/Stage and 2) actual experiments in a laboratory setting on autonomous vehicles.

Posted in: Robot motion planning, Robot task planning , Tagged:

A novel motion planning algorithm for robot navigation taking into account the robot kinematic constraints and shape

March 28, 2018 09:18 ,

Muhannad Mujahed, Dirk Fischer, Bärbel Mertsching, Admissible gap navigation: A new collision avoidance approach, Robotics and Autonomous Systems,
Volume 103, 2018, Pages 93-110, DOI: 10.1016/j.robot.2018.02.008.

This paper proposes a new concept, the Admissible Gap (AG), for reactive collision avoidance. A gap is called admissible if it is possible to find a collision-free motion control that guides a robot through it, while respecting the vehicle constraints. By utilizing this concept, a new navigation approach was developed, achieving an outstanding performance in unknown dense environments. Unlike the widely used gap-based methods, our approach directly accounts for the exact shape and kinematics, rather than finding a direction solution and turning it later into a collision-free admissible motion. The key idea is to analyze the structure of obstacles and virtually locate an admissible gap, once traversed, the robot makes progress towards the goal. For this purpose, we introduce a strategy of traversing gaps that respect the kinematic constraints and provides a compromise between path length and motion safety. We also propose a new methodology for extracting gaps that eliminates useless ones, thus reducing oscillations. Experimental results along with performance evaluation demonstrate the outstanding behavior of the proposed AG approach. Furthermore, a comparison with existing state-of-the-art methods shows that the AG approach achieves the best results in terms of efficiency, robustness, safety, and smoothness.

Posted in: Robot motion planning , Tagged: ,

A robotic wheelchair navigation algorithm that plans paths taking into account the discomfort of the user

March 28, 2018 09:07 ,

Yoichi Morales, Atsushi Watanabe, Florent Ferreri, Jani Even, Kazuhiro Shinozawa, Norihiro Hagita, Passenger discomfort map for autonomous navigation in a robotic wheelchair, Robotics and Autonomous Systems, Volume 103, 2018, Pages 13-26, DOI: 10.1016/j.robot.2018.02.002.

This work presents a navigational approach that takes into consideration the perception of comfort by a human passenger. Comfort is the state of being at ease and free from stress; thus, comfortable navigation is a ride that, in addition to being safe, is perceived by the passenger as being free from anxiety and stress. This study considers how to compute passenger comfortable paths. To compute such paths, passenger discomfort is studied in locations with good visibility and those with no visibility. In locations with good visibility, passenger preference to ride in the road is studied. For locations with non-visible areas, the relationship between passenger visibility and discomfort is studied. Autonomous-navigation experiments are performed to build a map of human discomfort that is used to compute global paths. A path planner is proposed that minimizes a three-variable cost function: location discomfort cost, area visibility cost, and path length cost. Planner parameters are calibrated toward a composite trajectory histogram built with data taken from participant self-driving trajectories. Finally, autonomous navigation experiments with 30 participants show that the proposed approach is rated as more comfortable than the state-of-the-art shortest planner approach.

Posted in: Robot motion planning , Tagged: ,

A novel method of mathematical compression of the value function for polynomial (in the state) time complexity of value iteration / policy iteration

March 27, 2018 09:01 ,

Alex Gorodetsky, Sertac Karaman, and Youssef Marzouk, High-dimensional stochastic optimal control using continuous tensor decompositions, The International Journal of Robotics Research Vol 37, Issue 2-3, pp. 340 – 377, DOI: 10.1177/0278364917753994.

Motion planning and control problems are embedded and essential in almost all robotics applications. These problems are often formulated as stochastic optimal control problems and solved using dynamic programming algorithms. Unfortunately, most existing algorithms that guarantee convergence to optimal solutions suffer from the curse of dimensionality: the run time of the algorithm grows exponentially with the dimension of the state space of the system. We propose novel dynamic programming algorithms that alleviate the curse of dimensionality in problems that exhibit certain low-rank structure. The proposed algorithms are based on continuous tensor decompositions recently developed by the authors. Essentially, the algorithms represent high-dimensional functions (e.g. the value function) in a compressed format, and directly perform dynamic programming computations (e.g. value iteration, policy iteration) in this format. Under certain technical assumptions, the new algorithms guarantee convergence towards optimal solutions with arbitrary precision. Furthermore, the run times of the new algorithms scale polynomially with the state dimension and polynomially with the ranks of the value function. This approach realizes substantial computational savings in “compressible” problem instances, where value functions admit low-rank approximations. We demonstrate the new algorithms in a wide range of problems, including a simulated six-dimensional agile quadcopter maneuvering example and a seven-dimensional aircraft perching example. In some of these examples, we estimate computational savings of up to 10 orders of magnitude over standard value iteration algorithms. We further demonstrate the algorithms running in real time on board a quadcopter during a flight experiment under motion capture.

Posted in: Probability and statistics, Robot motion planning , Tagged: , , , ,

using fuzzy Petri nets for mobile robot navigation

February 28, 2018 08:35 ,

Seung-yun Kim, Yilin Yang, A self-navigating robot using Fuzzy Petri nets, Robotics and Autonomous Systems, Volume 101, 2018, Pages 153-165, DOI: 10.1016/j.robot.2017.11.008.

Petri nets (PNs) are capable of modeling nearly any conceivable system and can provide a better understanding of the idealized action sequence in which to most effectively describe or execute said system through their powerful analytical capabilities. However, because real world instances are rarely as consistent and ideal as simulated models, basic PN modeling and simulation properties may be insufficient in practical application. We remedy this through specialization in Fuzzy Petri nets (FPNs). Fuzzy logic is incorporated to better model a self-navigating robot algorithm, thanks to its versatile multi-valued logic reasoning. By using FPNs, it is possible to simulate, assess, and communicate the process and reasoning of the navigational algorithm and apply it to real world programming. In this paper, we propose a series of specific fuzzy algorithms intended to be implemented in concert on a mobile robot platform in order to optimize the sequence of actions needed for a given task, primarily the navigation of an unknown maze. A set of varied maze configurations were developed and simulated as PN and FPN models, providing a testing environment to examine the efficiency of several methodologies. Five methods, including an original proposal in this paper, were compared across 30,000 simulations, evaluating in particular performance in processing cost in time. Our experiments concluded with results suggesting a very competitive task completion time at a considerable fraction in processing cost compared to the closest performing alternatives.

Posted in: Robot motion planning , Tagged: ,

Hybridizing RRT with deliberative path planning to improve performance

February 13, 2018 07:54 ,

Dong, Y., Camci, E. & Kayacan, Faster RRT-based Nonholonomic Path Planning in 2D Building Environments Using Skeleton-constrained Path Biasing, J Intell Robot Syst (2018) 89: 387, DOI: 10.1007/s10846-017-0567-9.

This paper presents a faster RRT-based path planning approach for regular 2-dimensional (2D) building environments. To minimize the planning time, we adopt the idea of biasing the RRT tree-growth in more focused ways. We propose to calculate the skeleton of the 2D environment first, then connect a geometrical path on the skeleton, and grow the RRT tree via the seeds generated locally along this path. We conduct batched simulations to find the universal parameters in manipulating the seeds generation. We show that the proposed skeleton-biased locally-seeded RRT (skilled-RRT) is faster than the other baseline planners (RRT, RRT*, A*-RRT, Theta*-RRT, and MARRT) through experimental tests using different vehicles in different 2D building environments. Given mild assumptions of the 2D environments, we prove that the proposed approach is probabilistically complete. We also present an application of the skilled-RRT for unmanned ground vehicle. Compared to the other baseline algorithms (Theta*-RRT and MARRT), we show the applicability and fast planning of the skilled-RRT in real environment.

Posted in: Robot motion planning , Tagged: ,

Achieving smooth motion in robotic manipulators on-line through their controller, and a nice state-of-the-art of the problem of smooth motion

February 7, 2018 08:52 ,

Yu-Sheng Lu, Yi-Yi Lin, Smooth motion control of rigid robotic manipulators with constraints on high-order kinematic variables, Mechatronics,
Volume 49, 2018, Pages 11-25, DOI: 10.1016/j.mechatronics.2017.11.003.

This paper presents a design for a jerk-constrained, time-optimal controller (JCTOC) that allows the smooth control of rigid robotic manipulators, in which time-optimal output responses are attained with confined jerk. A snap-constrained, time-optimal control (SCTOC) scheme is also proposed to produce even smoother output responses that are time-optimal, with a constraint on the maximum admissible snap. In contrast to conventional path-planning approaches that involve a bounded jerk/snap, the proposed JCTOC and SCTOC practically limit the corresponding high-order kinematic variables in real time. Using the structure of the computed torque control, the PD control, the JCTOC and the SCTOC are experimentally compared in terms of specific performance indices, including a chatter index, which is used to measure the unevenness of a signal.

Posted in: Control Engineering, Robot motion planning , Tagged:

On the drawbacks of RRT and how including deterministic sampling can help

January 31, 2018 08:05 ,

Lucas Janson, Brian Ichter, and Marco Pavone, Deterministic sampling-based motion planning: Optimality, complexity, and performance , The International Journal of Robotics Research Vol 37, Issue 1, pp. 46 – 61, DOI: 10.1177/0278364917714338.

Probabilistic sampling-based algorithms, such as the probabilistic roadmap (PRM) and the rapidly exploring random tree (RRT) algorithms, represent one of the most successful approaches to robotic motion planning, due to their strong theoretical properties (in terms of probabilistic completeness or even asymptotic optimality) and remarkable practical performance. Such algorithms are probabilistic in that they compute a path by connecting independently and identically distributed (i.i.d.) random points in the configuration space. Their randomization aspect, however, makes several tasks challenging, including certification for safety-critical applications and use of offline computation to improve real-time execution. Hence, an important open question is whether similar (or better) theoretical guarantees and practical performance could be obtained by considering deterministic, as opposed to random, sampling sequences. The objective of this paper is to provide a rigorous answer to this question. Specifically, we first show that PRM, for a certain selection of tuning parameters and deterministic low-dispersion sampling sequences, is deterministically asymptotically optimal, in other words, it returns a path whose cost converges deterministically to the optimal one as the number of points goes to infinity. Second, we characterize the convergence rate, and we find that the factor of sub-optimality can be very explicitly upper-bounded in terms of theℓ2 -dispersion of the sampling sequence and the connection radius of PRM. Third, we show that an asymptotically optimal version of PRM exists with computational and space complexity arbitrarily close to O(n) (the theoretical lower bound), where n is the number of points in the sequence. This is in contrast to the O(nlogn) complexity results for existing asymptotically optimal probabilistic planners. Fourth, we discuss extending our theoretical results and insights to other batch-processing algorithms such as FMT*, to non-uniform sampling strategies, to k-nearest-neighbor implementations, and to differentially constrained problems. Importantly, our main theoretical tool is the ℓ2-dispersion, an interesting consequence of which is that all our theoretical results also hold for low-ℓ2-dispersion random sampling (which i.i.d. sampling does not satisfy). In other words, achieving deterministic guarantees is really a matter of i.i.d. sampling versus non-i.i.d. low-dispersion sampling (with deterministic sampling as a prominent case), as opposed to random versus deterministic. Finally, through numerical experiments, we show that planning with deterministic (or random) low-dispersion sampling generally provides superior performance in terms of path cost and success rate.

Posted in: Robot motion planning , Tagged: ,

A new spatial transformation for planning mobile robot trajectories that guarantees a solution and also time requirement satisfaction

December 6, 2017 09:04 ,

S. G. Loizou, The Navigation Transformation, IEEE Transactions on Robotics, vol. 33, no. 6, pp. 1516-1523, DOI: 10.1109/TRO.2017.2725323.

This work introduces a novel approach to the solution of the navigation problem by mapping an obstacle-cluttered environment to a trivial domain called the point world, where the navigation task is reduced to connecting the images of the initial and destination configurations by a straight line. Due to this effect, the underlying transformation is termed the “navigation transformation.” The properties of the navigation transformation are studied in this work as well as its capability to provide-through the proposed feedback controller designs-solutions to the motion- and path-planning problems. Notably, the proposed approach enables the construction of temporal stabilization controllers as detailed herein, which provide a time abstraction to the navigation problem. The proposed solutions are correct by construction and, given a diffeomorphism from the workspace to a sphere world, tuning free. A candidate construction for the navigation transformation on sphere worlds is proposed. The provided theoretical results are backed by analytical proofs. The efficiency, robustness, and applicability of the proposed solutions are supported by a series of experimental case studies.

Posted in: Robot motion planning , Tagged: ,