On the need to replanning in POMDPs when applied to real systems, due to imperfect sensing and computational cost of online planning

October 4, 2018 08:27 ,

Ali-akbar Agha-mohammadi et al., SLAP: Simultaneous Localization and Planning Under Uncertainty via Dynamic Replanning in Belief Space, IEEE Transactions on Robotics, vol. 34, no. 5, DOI: 10.1109/TRO.2018.2838556.

Simultaneous localization and planning (SLAP) is a crucial ability for an autonomous robot operating under uncertainty. In its most general form, SLAP induces a continuous partially observable Markov decision process (POMDP), which needs to be repeatedly solved online. This paper addresses this problem and proposes a dynamic replanning scheme in belief space. The underlying POMDP, which is continuous in state, action, and observation space, is approximated offline via sampling-based methods, but operates in a replanning loop online to admit local improvements to the coarse offline policy. This construct enables the proposed method to combat changing environments and large localization errors, even when the change alters the homotopy class of the optimal trajectory. It further outperforms the state-of-the-art Feedback-based Information RoadMap (FIRM) method by eliminating unnecessary stabilization steps. Applying belief space planning to physical systems brings with it a plethora of challenges. A key focus of this paper is to implement the proposed planner on a physical robot and show the SLAP solution performance under uncertainty, in changing environments and in the presence of large disturbances, such as a kidnapped robot situation.

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

Interesting study of the number of optimal points in SLAM, considering it as a non-linear, non-convex optimization problem

September 27, 2018 09:27 ,

Heng Wang, Shoudong Huang, Guanghong Yang, Gamini Dissanayake, Comparison of two different objective functions in 2D point feature SLAM, Automatica,
Volume 97, 2018, Pages 172-181, DOI: 10.1016/j.automatica.2018.08.009.

This paper compares two different objective functions in 2D point feature Simultaneous Localization and Mapping (SLAM). It is shown that the objective function can have a significant impact on the convergence of the iterative optimization techniques used in SLAM. When Frobenius norm is adopted for the error term of the orientation part of odometry, the SLAM problem has much better convergence properties, as compared with that using the angle difference as the error term. For one-step case, we have proved that there is one and only one minimum to the SLAM problem, and strong duality always holds. For two-step case, strong duality always holds except when three very special conditions hold simultaneously (which happens with probability zero), thus the global optimal solution to primal SLAM problem can be obtained by solving the corresponding Lagrangian dual problem in most cases. Further, for arbitrary m-step cases, we also show using examples that much better convergence results can be obtained. Simulation examples are given to demonstrate the different convergence properties using two different objective functions.

Posted in: Mobile robot SLAM , Tagged: ,

On how psychological time emerges from execution of actions in the environment

September 26, 2018 09:24 ,

Jennifer T. Coull, Sylvie Droit-Volet, Explicit Understanding of Duration Develops Implicitly through Action, Trends in Cognitive Sciences, Volume 22, Issue 10, 2018, Pages 923-937, DOI: 10.1016/j.tics.2018.07.011.

Time is relative. Changes in cognitive state or sensory context make it appear to speed up or slow down. Our perception of time is a rather fragile mental construct derived from the way events in the world are processed and integrated in memory. Nevertheless, the slippery concept of time can be structured by draping it over more concrete functional scaffolding. Converging evidence from developmental studies of children and neuroimaging in adults indicates that we can represent time in spatial or motor terms. We hypothesise that explicit processing of time is mediated by motor structures of the brain in adulthood because we implicitly learn about time through action during childhood. Future challenges will be to harness motor or spatial representations of time to optimise behaviour, potentially for therapeutic gain.

Posted in: Psycho-physiological bases of engineering , Tagged:

A very interesting analysis on how reinforcement learning depends on time, both for MDPs and for the psychological basis of RL in the human brain

September 26, 2018 09:17 ,

Elijah A. Petter, Samuel J. Gershman, Warren H. Meck, Integrating Models of Interval Timing and Reinforcement Learning, Trends in Cognitive Sciences, Volume 22, Issue 10, 2018, Pages 911-922 DOI: 10.1016/j.tics.2018.08.004.

We present an integrated view of interval timing and reinforcement learning (RL) in the brain. The computational goal of RL is to maximize future rewards, and this depends crucially on a representation of time. Different RL systems in the brain process time in distinct ways. A model-based system learns ‘what happens when’, employing this internal model to generate action plans, while a model-free system learns to predict reward directly from a set of temporal basis functions. We describe how these systems are subserved by a computational division of labor between several brain regions, with a focus on the basal ganglia and the hippocampus, as well as how these regions are influenced by the neuromodulator dopamine.

Some quotes beyond the abstract:

The Markov assumption also makes explicit the requirements for temporal representation. All temporal dynamics must be captured by the state-transition function, which means that the state representation must encode the time-invariant structure of the environment.

Posted in: Psycho-physiological bases of engineering , Tagged: ,

A nice introduction to psychological time

September 26, 2018 09:13 ,

Lindsey Drayton, Moran Furman, Thy Mind, Thy Brain and Time, Trends in Cognitive Sciences, olume 22, Issue 10, 2018, Pages 841-843 DOI: 10.1016/j.tics.2018.08.007.

The passage of time has fascinated the human mind for millennia. Tools for measuring time emerged early in civilization: lunar calendars appear in the archeological record as far back as 10 000 years ago and water clocks some 6000 years ago. Later technological innovations such as mechanical clocks, and more recently atomic clocks, have allowed the tracking of time with ever-increasing precision. And yet, arguably, the most sophisticated ‘time piece’ is the brain. Our brains can not only track the duration and succession of events, but they can also coordinate complex motor movements at striking levels of precision; communicate effectively by generating and interpreting sounds and speech; determine how to maximize rewards over time in the face of uncertainty; reflect upon the past; plan for the future; respond to temporal regularities and irregularities in the environment; and adapt to change in temporal scales that range from millisecond resolution up to evolutionary processes spanning millions of years.

Posted in: Cognitive sciences , Tagged: ,

A performance metric for evaluating and comparing robot navigation algorithms

September 21, 2018 08:31 ,

Yazhini Chitra Pradeep, Kendrick Amezquita-Semprun, Manuel Del Rosario, Peter C.Y. Chen, The Pc metric: A performance measure for collision avoidance algorithms, Robotics and Autonomous Systems, Volume 109, 2018, Pages 125-138, DOI: 10.1016/j.robot.2018.08.005.

Despite the comprehensive development in the field of navigation algorithms for mobile robots, the research on performance metrics and evaluation procedures for making standardized quantitative comparison between different algorithms has gained attention only recently. This work attempts to contribute with such effort by introducing a performance metric for the assessment of collision avoidance algorithms for mobile robots. The proposed metric comprehensively evaluates the actions taken by the objects and their consequences, in a given scenario of any given collision avoidance algorithm, based on the concept of probability of collision. The contribution of the paper encompasses the definition of the metric, the methodology to estimate the metric, and the framework to apply the metric for any given scenario. Experiments and numerical simulations are conducted to validate and demonstrate the effectiveness of the proposed metric in performance evaluation and comparison among different collision avoidance algorithms.

Posted in: Robot motion planning

A novel hybridization of semantic and topological maps applied to mapping and localization in outdoors

September 21, 2018 08:26 ,

Fernando Bernuy, Javier Ruiz-del-Solar, Topological Semantic Mapping and Localization in Urban Road Scenarios, Journal of Intelligent & Robotic Systems, September 2018, Volume 92, Issue 1, pp 19–32, DOI: 10.1007/s10846-017-0744-x.

Autonomous vehicle self-localization must be robust to environment changes, such as dynamic objects, variable illumination, and atmospheric conditions. Topological maps provide a concise representation of the world by only keeping information about relevant places, being robust to environment changes. On the other hand, semantic maps correspond to a high level representation of the environment that includes labels associated with relevant objects and places. Hence, the use of a topological map based on semantic information represents a robust and efficient solution for large-scale outdoor scenes for autonomous vehicles and Advanced Driver Assistance Systems (ADAS). In this work, a novel topological semantic mapping and localization methodology for large-scale outdoor scenarios for autonomous driving and ADAS applications is presented. The methodology uses: (i) a deep neural network for obtaining semantic observations of the environment, (ii) a Topological Semantic Map (TSM) for storing selected semantic observations, and (iii) a topological localization algorithm which uses a Particle Filter for obtaining the vehicle’s pose in the TSM. The proposed methodology was tested on a real driving scenario, where a True Estimate Rate of the vehicle’s pose of 96.9% and a Mean Position Accuracy of 7.7[m] were obtained. These results are much better than the ones obtained by other two methods used for comparative purposes. Experiments also show that the method is able to obtain the pose of the vehicle when its initial pose is unknown.

Posted in: Mobile robot SLAM , Tagged: , ,

A nice hybridization of RBPF, high-frequency scan matching and topological maps to perform SLAM, with an also nice state-of-the-art

September 19, 2018 08:52 ,

Aristeidis G. Thallas, Emmanouil G. Tsardoulias, Loukas Petrou, Topological Based Scan Matching – Odometry Posterior Sampling in RBPF Under Kinematic Model Failures, Journal of Intelligent & Robotic Systems, September 2018, Volume 91, Issue 3–4, pp 543–568, DOI: 10.1007/s10846-017-0730-3.

Rao-Blackwellized Particle Filters (RBPF) have been utilized to provide a solution to the SLAM problem. One of the main factors that cause RBPF failure is the potential particle impoverishment. Another popular approach to the SLAM problem are Scan Matching methods, whose good results require environments with lots of information, however fail in the lack thereof. To face these issues, in the current work techniques are presented to combine Rao-Blackwellized particle filters with a scan matching algorithm (CRSM SLAM). The particle filter maintains the correct hypothesis in environments lacking features and CRSM is employed in feature-rich environments while simultaneously reduces the particle filter dispersion. Since CRSM’s good performance is based on its high iteration frequency, a multi-threaded combination is presented which allows CRSM to operate while RBPF updates its particles. Additionally, a novel method utilizing topological information is proposed, in order to reduce the number of particle filter resamplings. Finally, we present methods to address anomalous situations where scan matching can not be performed and the vehicle displays behaviors not modeled by the kinematic model, causing the whole method to collapse. Numerous experiments are conducted to support the aforementioned methods’ advantages.

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

Using reasoning to improve low-level robot navigation

September 19, 2018 08:47 ,

Muhayyuddin, Aliakbar AkbariJan Rosell, A Real-Time Path-Planning Algorithm based on Receding Horizon Techniques, Journal of Intelligent & Robotic Systems, September 2018, Volume 91, Issue 3–4, pp 459–477, DOI: 10.1007/s10846-017-0698-z.

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.

Posted in: Robot motion planning , Tagged: , ,

A unifying framework for path planning in real-time (mainly for UAVs) and a nice summary of the state-of-the-art in modern path planning

September 19, 2018 08:42 ,

M. Murillo, G. SánchezL. GenzelisL. Giovanini, A Real-Time Path-Planning Algorithm based on Receding Horizon Techniques, Journal of Intelligent & Robotic Systems, September 2018, Volume 91, Issue 3–4, pp 445–457, DOI: 10.1007/s10846-017-0740-1.

In this article we present a real-time path-planning algorithm that can be used to generate optimal and feasible paths for any kind of unmanned vehicle (UV). The proposed algorithm is based on the use of a simplified particle vehicle (PV) model, which includes the basic dynamics and constraints of the UV, and an iterated non-linear model predictive control (NMPC) technique that computes the optimal velocity vector (magnitude and orientation angles) that allows the PV to move toward desired targets. The computed paths are guaranteed to be feasible for any UV because: i) the PV is configured with similar characteristics (dynamics and physical constraints) as the UV, and ii) the feasibility of the optimization problem is guaranteed by the use of the iterated NMPC algorithm. As demonstration of the capabilities of the proposed path-planning algorithm, we explore several simulation examples in different scenarios. We consider the existence of static and dynamic obstacles and a follower condition.

Posted in: Robot motion planning , Tagged: ,