Category Archives: Robotics

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: ,

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: ,

Including the dynamics of the environment in robot motion planning (navigation)

September 4, 2018 15:10 ,

María-Teresa Lorente, Eduardo Owen, and Luis Montano, Model-based robocentric planning and navigation for dynamic environments, The International Journal of Robotics Research Vol 37, Issue 8, pp. 867 – 889 DOI: 10.1177/0278364918775520.

This work addresses a new technique of motion planning and navigation for differential-drive robots in dynamic environments. Static and dynamic objects are represented directly on the control space of the robot, where decisions on the best motion are made. A new model representing the dynamism and the prediction of the future behavior of the environment is defined, the dynamic object velocity space (DOVS). A formal definition of this model is provided, establishing the properties for its characterization. An analysis of its complexity, compared with other methods, is performed. The model contains information about the future behavior of obstacles, mapped on the robot control space. It allows planning of near-time-optimal safe motions within the visibility space horizon, not only for the current sampling period. Navigation strategies are developed based on the identification of situations in the model. The planned strategy is applied and updated for each sampling time, adapting to changes occurring in the scenario. The technique is evaluated in randomly generated simulated scenarios, based on metrics defined using safety and time-to-goal criteria. An evaluation in real-world experiments is also presented.

Posted in: Robot motion planning , Tagged:

A probabilistically rigurous formulation of the estimation of grid maps in dynamic scenarios, and a nice review and state-of-the-art of grid maps, both for static and dynamic scenarios

September 4, 2018 15:08 ,

Dominik Nuss, Stephan Reuter, Markus Thom, Ting Yuan, Gunther Krehl, Michael Maile, Axel Gern, and Klaus Dietmayer, A random finite set approach for dynamic occupancy grid maps with real-time application, The International Journal of Robotics Research
Vol 37, Issue 8, pp. 841 – 866, DOI: 10.1177/0278364918775523.

Grid mapping is a well-established approach for environment perception in robotic and automotive applications. Early work suggests estimating the occupancy state of each grid cell in a robot’s environment using a Bayesian filter to recursively combine new measurements with the current posterior state estimate of each grid cell. This filter is often referred to as binary Bayes filter. A basic assumption of classical occupancy grid maps is a stationary environment. Recent publications describe bottom-up approaches using particles to represent the dynamic state of a grid cell and outline prediction-update recursions in a heuristic manner. This paper defines the state of multiple grid cells as a random finite set, which allows to model the environment as a stochastic, dynamic system with multiple obstacles, observed by a stochastic measurement system. It motivates an original filter called the probability hypothesis density / multi-instance Bernoulli (PHD/MIB) filter in a top-down manner. The paper presents a real-time application serving as a fusion layer for laser and radar sensor data and describes in detail a highly efficient parallel particle filter implementation. A quantitative evaluation shows that parameters of the stochastic process model affect the filter results as theoretically expected and that appropriate process and observation models provide consistent state estimation results.

Posted in: Mobile robot mapping , Tagged: , ,

Considering the robot and all the intermmediate objects that participate in the manipulation of another object as a MDP

September 3, 2018 15:58 ,

Yilun Zhou, Benjamin Burchfiel, George Konidaris, Representing, learning, and controlling complex object interactions, Autonomous Robots, Volume 42, Issue 7, pp 1355–1367, DOI: 10.1007/s1051.

We present a framework for representing scenarios with complex object interactions, where a robot cannot directly interact with the object it wishes to control and must instead influence it via intermediate objects. For instance, a robot learning to drive a car can only change the car’s pose indirectly via the steering wheel, and must represent and reason about the relationship between its own grippers and the steering wheel, and the relationship between the steering wheel and the car. We formalize these interactions as chains and graphs of Markov decision processes (MDPs) and show how such models can be learned from data. We also consider how they can be controlled given known or learned dynamics. We show that our complex model can be collapsed into a single MDP and solved to find an optimal policy for the combined system. Since the resulting MDP may be very large, we also introduce a planning algorithm that efficiently produces a potentially suboptimal policy. We apply these models to two systems in which a robot uses learning from demonstration to achieve indirect control: playing a computer game using a joystick, and using a hot water dispenser to heat a cup of water.

Posted in: Robot task planning , Tagged: ,

Loop closure detection by optimization of finite sets of images that correspond to each place

September 3, 2018 15:53 ,

Han, F., Wang, H., Huang, G. et al, Sequence-based sparse optimization methods for long-term loop closure detection in visual SLAM, Autonomous Robots, Volume 42, Issue 7, pp 1323–1335, DOI: 10.1007/s1051.

Loop closure detection is one of the most important module in Simultaneously Localization and Mapping (SLAM) because it enables to find the global topology among different places. A loop closure is detected when the current place is recognized to match the previous visited places. When the SLAM is executed throughout a long-term period, there will be additional challenges for the loop closure detection. The illumination, weather, and vegetation conditions can often change significantly during the life-long SLAM, resulting in the critical strong perceptual aliasing and appearance variation problems in loop closure detection. In order to address this problem, we propose a new Robust Multimodal Sequence-based (ROMS) method for robust loop closure detection in long-term visual SLAM. A sequence of images is used as the representation of places in our ROMS method, where each image in the sequence is encoded by multiple feature modalites so that different places can be recognized discriminatively. We formulate the robust place recognition problem as a convex optimization problem with structured sparsity regularization due to the fact that only a small set of template places can match the query place. In addition, we also develop a new algorithm to solve the formulated optimization problem efficiently, which guarantees to converge to the global optima theoretically. Our ROMS method is evaluated through extensive experiments on three large-scale benchmark datasets, which record scenes ranging from different times of the day, months, and seasons. Experimental results demonstrate that our ROMS method outperforms the existing loop closure detection methods in long-term SLAM, and achieves the state-of-the-art performance.

Posted in: Mobile robot SLAM , Tagged: