Category Archives: Robotics

Using two different environment representations: a detailed one for SLAM, a coarse one for selecting actions for active perception

February 11, 2018 09:12 ,

Nelson, E., Corah, M. & Michael, N., Environment model adaptation for mobile robot exploration,Auton Robot (2018) 42: 257, DOI: 10.1007/s10514-017-9669-2.

In this work, we propose a methodology to adapt a mobile robot’s environment model during exploration as a means of decreasing the computational complexity associated with information metric evaluation and consequently increasing the speed at which the system is able to plan actions and travel through an unknown region given finite computational resources. Recent advances in exploration compute control actions by optimizing information-theoretic metrics on the robot’s map. These metrics are generally computationally expensive to evaluate, limiting the speed at which a robot is able to explore. To reduce computational cost, we propose keeping two representations of the environment: one full resolution representation for planning and collision checking, and another with a coarse resolution for rapidly evaluating the informativeness of planned actions. To generate the coarse representation, we employ the Principal of Relevant Information from rate distortion theory to compress a robot’s occupancy grid map. We then propose a method for selecting a coarse representation that sacrifices a minimal amount of information about expected future sensor measurements using the Information Bottleneck Method. We outline an adaptive strategy that changes the robot’s environment representation in response to its surroundings to maximize the computational efficiency of exploration. On computationally constrained systems, this reduction in complexity enables planning over longer predictive horizons, leading to faster navigation. We simulate and experimentally evaluate mutual information based exploration through cluttered indoor environments with exploration rates that adapt based on environment complexity leading to an order-of-magnitude increase in the maximum rate of exploration in contrast to non-adaptive techniques given the same finite computational resources.

Posted in: Mobile robot SLAM, Robotics , Tagged: ,

A novel approach to use POMDP in practical active perception, where rewards are needed to penalize uncertainty and therefore reomve the piecewise-linear and convex property of the value function

February 11, 2018 09:08 ,

Satsangi, Y., Whiteson, S., Oliehoek, F.A. et al., Exploiting submodular value functions for scaling up active perception, Auton Robot (2018) 42: 209, DOI: 10.1007/s10514-017-9666-5.

In active perception tasks, an agent aims to select sensory actions that reduce its uncertainty about one or more hidden variables. For example, a mobile robot takes sensory actions to efficiently navigate in a new environment. While partially observable Markov decision processes (POMDPs) provide a natural model for such problems, reward functions that directly penalize uncertainty in the agent’s belief can remove the piecewise-linear and convex (PWLC) property of the value function required by most POMDP planners. Furthermore, as the number of sensors available to the agent grows, the computational cost of POMDP planning grows exponentially with it, making POMDP planning infeasible with traditional methods. In this article, we address a twofold challenge of modeling and planning for active perception tasks. We analyze ρ POMDP and POMDP-IR, two frameworks for modeling active perception tasks, that restore the PWLC property of the value function. We show the mathematical equivalence of these two frameworks by showing that given a ρ POMDP along with a policy, they can be reduced to a POMDP-IR and an equivalent policy (and vice-versa). We prove that the value function for the given ρ POMDP (and the given policy) and the reduced POMDP-IR (and the reduced policy) is the same. To efficiently plan for active perception tasks, we identify and exploit the independence properties of POMDP-IR to reduce the computational cost of solving POMDP-IR (and ρ POMDP). We propose greedy point-based value iteration (PBVI), a new POMDP planning method that uses greedy maximization to greatly improve scalability in the action space of an active perception POMDP. Furthermore, we show that, under certain conditions, including submodularity, the value function computed using greedy PBVI is guaranteed to have bounded error with respect to the optimal value function. We establish the conditions under which the value function of an active perception POMDP is guaranteed to be submodular. Finally, we present a detailed empirical analysis on a dataset collected from a multi-camera tracking system employed in a shopping mall. Our method achieves similar performance to existing methods but at a fraction of the computational cost leading to better scalability for solving active perception tasks.

Posted in: Probability and statistics, Robotics , Tagged: ,

A nice review on the topic of active perception

February 11, 2018 09:04 ,

Ruzena BajcsyYiannis AloimonosJohn K. Tsotsos, Revisiting active perception, Auton Robot (2018) 42: 177, DOI: 10.1007/s10514-017-9615-3.

Despite the recent successes in robotics, artificial intelligence and computer vision, a complete artificial agent necessarily must include active perception. A multitude of ideas and methods for how to accomplish this have already appeared in the past, their broader utility perhaps impeded by insufficient computational power or costly hardware. The history of these ideas, perhaps selective due to our perspectives, is presented with the goal of organizing the past literature and highlighting the seminal contributions. We argue that those contributions are as relevant today as they were decades ago and, with the state of modern computational tools, are poised to find new life in the robotic perception systems of the next decade.

Posted in: Robotics , 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:

Extending STRIPS-like symbolic planners with metrical/physical constraints for the domain of robotic manipulation

January 31, 2018 08:37 ,

Caelan Reed Garrett, Tomás Lozano-Pérez, and Leslie Pack Kaelbling, FFRob: Leveraging symbolic planning for efficient task and motion planning, The International Journal of Robotics Research Vol 37, Issue 1, pp. 104 – 136, DOI: 10.1177/0278364917739114
.

Mobile manipulation problems involving many objects are challenging to solve due to the high dimensionality and multi-modality of their hybrid configuration spaces. Planners that perform a purely geometric search are prohibitively slow for solving these problems because they are unable to factor the configuration space. Symbolic task planners can efficiently construct plans involving many variables but cannot represent the geometric and kinematic constraints required in manipulation. We present the FFRob algorithm for solving task and motion planning problems. First, we introduce extended action specification (EAS) as a general purpose planning representation that supports arbitrary predicates as conditions. We adapt existing heuristic search ideas for solving strips planning problems, particularly delete-relaxations, to solve EAS problem instances. We then apply the EAS representation and planners to manipulation problems resulting in FFRob. FFRob iteratively discretizes task and motion planning problems using batch sampling of manipulation primitives and a multi-query roadmap structure that can be conditionalized to evaluate reachability under different placements of movable objects. This structure enables the EAS planner to efficiently compute heuristics that incorporate geometric and kinematic planning constraints to give a tight estimate of the distance to the goal. Additionally, we show FFRob is probabilistically complete and has a finite expected runtime. Finally, we empirically demonstrate FFRob’s effectiveness on complex and diverse task and motion planning tasks including rearrangement planning and navigation among movable objects.

Posted in: Industrial robots, Robot task planning , Tagged: ,

Using sequences of images for loop closure instead of only one

January 31, 2018 08:08 ,

Loukas Bampis, Angelos Amanatiadis, and Antonios Gasteratos, Fast loop-closure detection using visual-word-vectors from image sequences, The International Journal of Robotics Research Vol 37, Issue 1, pp. 62 – 82, DOI: 10.1177/0278364917740639.

In this paper, a novel pipeline for loop-closure detection is proposed. We base our work on a bag of binary feature words and we produce a description vector capable of characterizing a physical scene as a whole. Instead of relying on single camera measurements, the robot’s trajectory is dynamically segmented into image sequences according to its content. The visual word occurrences from each sequence are then combined to create sequence-visual-word-vectors and provide additional information to the matching functionality. In this way, scenes with considerable visual differences are firstly discarded, while the respective image-to-image associations are provided subsequently. With the purpose of further enhancing the system’s performance, a novel temporal consistency filter (trained offline) is also introduced to advance matches that persist over time. Evaluation results prove that the presented method compares favorably with other state-of-the-art techniques, while our algorithm is tested on a tablet device, verifying the computational efficiency of the approach.

Posted in: Mobile robot SLAM , 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: ,

Probabilistic SLAM is still the way to go for dynamic environments (according to this paper)

January 18, 2018 08:01 ,

C. Evers and P. A. Naylor, Optimized Self-Localization for SLAM in Dynamic Scenes Using Probability Hypothesis Density Filters, IEEE Transactions on Signal Processing, vol. 66, no. 4, pp. 863-878, DOI: 10.1109/TSP.2017.2775590.

In many applications, sensors that map the positions of objects in unknown environments are installed on dynamic platforms. As measurements are relative to the observer’s sensors, scene mapping requires accurate knowledge of the observer state. However, in practice, observer reports are subject to positioning errors. Simultaneous localization and mapping addresses the joint estimation problem of observer localization and scene mapping. State-of-the-art approaches typically use visual or optical sensors and therefore rely on static beacons in the environment to anchor the observer estimate. However, many applications involving sensors that are not conventionally used for Simultaneous Localization and Mapping (SLAM) are affected by highly dynamic scenes, such that the static world assumption is invalid. This paper proposes a novel approach for dynamic scenes, called GEneralized Motion (GEM) SLAM. Based on probability hypothesis density filters, the proposed approach probabilistically anchors the observer state by fusing observer information inferred from the scene with reports of the observer motion. This paper derives the general, theoretical framework for GEM-SLAM, and shows that it generalizes existing Probability Hypothesis Density (PHD)-based SLAM algorithms. Simulations for a model-specific realization using range-bearing sensors and multiple moving objects highlight that GEM-SLAM achieves significant improvements over three benchmark algorithms.

Posted in: Bayesian filtering, Mobile robot SLAM , Tagged: ,

Reinforcement learning to recover legged robots from damages

January 9, 2018 10:42 ,

Konstantinos Chatzilygeroudis, Vassilis Vassiliades, Jean-Baptiste Mouret, Reset-free Trial-and-Error Learning for Robot Damage Recovery, Robotics and Autonomous Systems, Volume 100, 2018, Pages 236-250, DOI: 10.1016/j.robot.2017.11.010.

The high probability of hardware failures prevents many advanced robots (e.g., legged robots) from being confidently deployed in real-world situations (e.g., post-disaster rescue). Instead of attempting to diagnose the failures, robots could adapt by trial-and-error in order to be able to complete their tasks. In this situation, damage recovery can be seen as a Reinforcement Learning (RL) problem. However, the best RL algorithms for robotics require the robot and the environment to be reset to an initial state after each episode, that is, the robot is not learning autonomously. In addition, most of the RL methods for robotics do not scale well with complex robots (e.g., walking robots) and either cannot be used at all or take too long to converge to a solution (e.g., hours of learning). In this paper, we introduce a novel learning algorithm called “Reset-free Trial-and-Error” (RTE) that (1) breaks the complexity by pre-generating hundreds of possible behaviors with a dynamics simulator of the intact robot, and (2) allows complex robots to quickly recover from damage while completing their tasks and taking the environment into account. We evaluate our algorithm on a simulated wheeled robot, a simulated six-legged robot, and a real six-legged walking robot that are damaged in several ways (e.g., a missing leg, a shortened leg, faulty motor, etc.) and whose objective is to reach a sequence of targets in an arena. Our experiments show that the robots can recover most of their locomotion abilities in an environment with obstacles, and without any human intervention.

Posted in: Applications of reinforcement learning to robots

SLAM based on intervals

January 9, 2018 10:37 ,

Mohamed Mustafa, Alexandru Stancu, Nicolas Delanoue, Eduard Codres, Guaranteed SLAM—An interval approach, Robotics and Autonomous Systems, Volume 100, 2018, Pages 160-170, DOI: 10.1016/j.robot.2017.11.009.

This paper proposes a new approach, interval Simultaneous Localization and Mapping (i-SLAM), which addresses the robotic mapping problem in the context of interval methods, where the robot sensor noise is assumed bounded. With no prior knowledge about the noise distribution or its probability density function, we derive and present necessary conditions to guarantee the map convergence even in the presence of nonlinear observation and motion models. These conditions may require the presence of some anchoring landmarks with known locations. The performance of i-SLAM is compared with the probabilistic counterparts in terms of accuracy and efficiency.

Posted in: Mobile robot SLAM