Category Archives: Robotics

Survey and taxonomy of path planning algorithms

Thi Thoa Mac, Cosmin Copot, Duc Trung Tran, Robin De Keyser, Heuristic approaches in robot path planning: A survey, Robotics and Autonomous Systems, Volume 86, 2016, Pages 13-28, ISSN 0921-8890, DOI: 10.1016/j.robot.2016.08.001.

Autonomous navigation of a robot is a promising research domain due to its extensive applications. The navigation consists of four essential requirements known as perception, localization, cognition and path planning, and motion control in which path planning is the most important and interesting part. The proposed path planning techniques are classified into two main categories: classical methods and heuristic methods. The classical methods consist of cell decomposition, potential field method, subgoal network and road map. The approaches are simple; however, they commonly consume expensive computation and may possibly fail when the robot confronts with uncertainty. This survey concentrates on heuristic-based algorithms in robot path planning which are comprised of neural network, fuzzy logic, nature-inspired algorithms and hybrid algorithms. In addition, potential field method is also considered due to the good results. The strengths and drawbacks of each algorithm are discussed and future outline is provided.

Globally optimal ICP

J. Yang, H. Li, D. Campbell and Y. Jia, “Go-ICP: A Globally Optimal Solution to 3D ICP Point-Set Registration,” in IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 38, no. 11, pp. 2241-2254, Nov. 1 2016. DOI: 10.1109/TPAMI.2015.2513405.

The Iterative Closest Point (ICP) algorithm is one of the most widely used methods for point-set registration. However, being based on local iterative optimization, ICP is known to be susceptible to local minima. Its performance critically relies on the quality of the initialization and only local optimality is guaranteed. This paper presents the first globally optimal algorithm, named Go-ICP, for Euclidean (rigid) registration of two 3D point-sets under the $L_2$ error metric defined in ICP. The Go-ICP method is based on a branch-and-bound scheme that searches the entire 3D motion space $SE(3)$ . By exploiting the special structure of $SE(3)$ geometry, we derive novel upper and lower bounds for the registration error function. Local ICP is integrated into the BnB scheme, which speeds up the new method while guaranteeing global optimality. We also discuss extensions, addressing the issue of outlier robustness. The evaluation demonstrates that the proposed method is able to produce reliable registration results regardless of the initialization. Go-ICP can be applied in scenarios where an optimal solution is desirable or where a good initialization is not always available.

Learning from demonstration through inverse reinforcement learning enhaced with neural network for generalizing demonstrations and improve visiting of states

Chen Xia, Abdelkader El Kamel, Neural inverse reinforcement learning in autonomous navigation, Robotics and Autonomous Systems, Volume 84, 2016, Pages 1-14, ISSN 0921-8890, DOI: 10.1016/j.robot.2016.06.003.

Designing intelligent and robust autonomous navigation systems remains a great challenge in mobile robotics. Inverse reinforcement learning (IRL) offers an efficient learning technique from expert demonstrations to teach robots how to perform specific tasks without manually specifying the reward function. Most of existing IRL algorithms assume the expert policy to be optimal and deterministic, and are applied to experiments with relatively small-size state spaces. However, in autonomous navigation tasks, the state spaces are frequently large and demonstrations can hardly visit all the states. Meanwhile the expert policy may be non-optimal and stochastic. In this paper, we focus on IRL with large-scale and high-dimensional state spaces by introducing the neural network to generalize the expert’s behaviors to unvisited regions of the state space and an explicit policy representation is easily expressed by neural network, even for the stochastic expert policy. An efficient and convenient algorithm, Neural Inverse Reinforcement Learning (NIRL), is proposed. Experimental results on simulated autonomous navigation tasks show that a mobile robot using our approach can successfully navigate to the target position without colliding with unpredicted obstacles, largely reduce the learning time, and has a good generalization performance on undemonstrated states. Hence prove the robot intelligence of autonomous navigation transplanted from limited demonstrations to completely unknown tasks.

Mapping (and navitating in) outdoor unstructured environments with low-cost and few sensors, using relations between landmarks instead of absolute or metrical positions

Mark McClelland, Mark Campbell, Tara Estlin, Qualitative relational mapping and navigation for planetary rovers, Robotics and Autonomous Systems, Volume 83, 2016, Pages 73-86, ISSN 0921-8890, DOI: j.robot.2016.05.017.

This paper presents a novel method for qualitative mapping of large scale spaces which decouples the mapping problem from that of position estimation. The proposed framework makes use of a graphical representation of the world in order to build a map consisting of qualitative constraints on the geometric relationships between landmark triplets. This process allows a mobile robot to extract information about landmark positions using a set of minimal sensors in the absence of GPS. A novel measurement method based on camera imagery is presented which extends previous work from the field of Qualitative Spatial Reasoning. A Branch-and-Bound approach is taken to solve a set of non-convex feasibility problems required for generating off-line operator lookup tables and on-line measurements, which are fused into the map using an iterative graph update. A navigation approach for travel between distant landmarks is developed, using estimates of the Relative Neighborhood Graph extracted from the qualitative map in order to generate a sequence of landmark objectives based on proximity. Average and asymptotic performance of the mapping algorithm is evaluated using Monte Carlo tests on randomly generated maps, and a data-driven simulation is presented for a robot traversing the Jet Propulsion Laboratory Mars Yard while building a relational map. These results demonstrate that the system can be effectively used to build a map sufficiently complete and accurate for long-distance navigation as well as other applications.

Sample-based approximation to POMDPs integrated with forward simulation for robot active exploration, with a nice related work about active exploration in robotics

Mikko Lauri, Risto Ritala, Planning for robotic exploration based on forward simulation, Robotics and Autonomous Systems, Volume 83, 2016, Pages 15-31, ISSN 0921-8890, DOI: 10.1016/j.robot.2016.06.008.

We address the problem of controlling a mobile robot to explore a partially known environment. The robot’s objective is the maximization of the amount of information collected about the environment. We formulate the problem as a partially observable Markov decision process (POMDP) with an information-theoretic objective function, and solve it applying forward simulation algorithms with an open-loop approximation. We present a new sample-based approximation for mutual information useful in mobile robotics. The approximation can be seamlessly integrated with forward simulation planning algorithms. We investigate the usefulness of POMDP based planning for exploration, and to alleviate some of its weaknesses propose a combination with frontier based exploration. Experimental results in simulated and real environments show that, depending on the environment, applying POMDP based planning for exploration can improve performance over frontier exploration.

Learning concepts from graphs in robotics, through first-order logic and discovery of subgraphs, forming arbitrary hierarchies

Ana C. Tenorio-González, Eduardo F. Morales, Automatic discovery of relational concepts by an incremental graph-based representation, Robotics and Autonomous Systems, Volume 83, 2016, Pages 1-14, ISSN 0921-8890, DOI: 10.1016/j.robot.2016.06.012.

Automatic discovery of concepts has been an elusive area in machine learning. In this paper, we describe a system, called ADC, that automatically discovers concepts in a robotics domain, performing predicate invention. Unlike traditional approaches of concept discovery, our approach automatically finds and collects instances of potential relational concepts. An agent, using ADC, creates an incremental graph-based representation with the information it gathers while exploring its environment, from which common sub-graphs are identified. The subgraphs discovered are instances of potential relational concepts which are induced with Inductive Logic Programming and predicate invention. Several concepts can be induced concurrently and the learned concepts can form arbitrarily hierarchies. The approach was tested for learning concepts of polygons, furniture, and floors of buildings with a simulated robot and compared with concepts suggested by users.

Survey of model-based reinforcement learning (and of reinforcement learning in general), for its application to improve learning time in robotics; a lot of references but not so many -or clear- explanations

Athanasios S. Polydoros, Lazaros Nalpantidis, Survey of Model-Based Reinforcement Learning: Applications on Robotics, Journal of Intelligent & Robotic Systems, May 2017, Volume 86, Issue 2, pp 153–173, DOI: 10.1007/s10846-017-0468-y.

Reinforcement learning is an appealing approach for allowing robots to learn new tasks. Relevant literature reveals a plethora of methods, but at the same time makes clear the lack of implementations for dealing with real life challenges. Current expectations raise the demand for adaptable robots. We argue that, by employing model-based reinforcement learning, the—now limited—adaptability characteristics of robotic systems can be expanded. Also, model-based reinforcement learning exhibits advantages that makes it more applicable to real life use-cases compared to model-free methods. Thus, in this survey, model-based methods that have been applied in robotics are covered. We categorize them based on the derivation of an optimal policy, the definition of the returns function, the type of the transition model and the learned task. Finally, we discuss the applicability of model-based reinforcement learning approaches in new applications, taking into consideration the state of the art in both algorithms and hardware.

Emergence of symbols in robotics as a “new” area of research in developmental robotics: a survey

Tadahiro Taniguchi, Takayuki Nagai, Tomoaki Nakamura, Naoto Iwahashi, Tetsuya Ogata, Hideki Asoh, Symbol Emergence in Robotics: A Survey, arXiv:1509.08973.

Humans can learn the use of language through physical interaction with their environment and semiotic communication with other people. It is very important to obtain a computational understanding of how humans can form a symbol system and obtain semiotic skills through their autonomous mental development. Recently, many studies have been conducted on the construction of robotic systems and machine-learning methods that can learn the use of language through embodied multimodal interaction with their environment and other systems. Understanding human social interactions and developing a robot that can smoothly communicate with human users in the long term, requires an understanding of the dynamics of symbol systems and is crucially important. The embodied cognition and social interaction of participants gradually change a symbol system in a constructive manner. In this paper, we introduce a field of research called symbol emergence in robotics (SER). SER is a constructive approach towards an emergent symbol system. The emergent symbol system is socially self-organized through both semiotic communications and physical interactions with autonomous cognitive developmental agents, i.e., humans and developmental robots. Specifically, we describe some state-of-art research topics concerning SER, e.g., multimodal categorization, word discovery, and a double articulation analysis, that enable a robot to obtain words and their embodied meanings from raw sensory–motor information, including visual information, haptic information, auditory information, and acoustic speech signals, in a totally unsupervised manner. Finally, we suggest future directions of research in SER.

Combination of several mobile robot localization methods in order to achieve high accuracy in industrial environments, with interesting figures for current localization accuracy achievable by standard solutions

Goran Vasiljevi, Damjan Mikli, Ivica Draganjac, Zdenko Kovai, Paolo Lista, High-accuracy vehicle localization for autonomous warehousing, Robotics and Computer-Integrated Manufacturing, Volume 42, December 2016, Pages 1-16, ISSN 0736-5845, DOI: 10.1016/j.rcim.2016.05.001.

The research presented in this paper aims to bridge the gap between the latest scientific advances in autonomous vehicle localization and the industrial state of the art in autonomous warehousing. Notwithstanding great scientific progress in the past decades, industrial autonomous warehousing systems still rely on external infrastructure for obtaining their precise location. This approach increases warehouse installation costs and decreases system reliability, as it is sensitive to measurement outliers and the external localization infrastructure can get dirty or damaged. Several approaches, well studied in scientific literature, are capable of determining vehicle position based only on information provided by on board sensors, most commonly wheel encoders and laser scanners. However, scientific results published to date either do not provide sufficient accuracy for industrial applications, or have not been extensively tested in realistic, industrial-like operating conditions. In this paper, we combine several well established algorithms into a high-precision localization pipeline, capable of computing the pose of an autonomous forklift to sub-centimeter precision. The algorithms use only odometry information from wheel encoders and range readings from an on board laser scanner. The effectiveness of the proposed solution is evaluated by an extensive experiment that lasted for several days, and was performed in a realistic industrial-like environment.

Integration of the ICP algorithm with a Kalman filter to improve relative localization, with a good state-of-the-art of ICP algorithms

F. Aghili and C. Y. Su, “Robust Relative Navigation by Integration of ICP and Adaptive Kalman Filter Using Laser Scanner and IMU,” in IEEE/ASME Transactions on Mechatronics, vol. 21, no. 4, pp. 2015-2026, Aug. 2016.DOI: 10.1109/TMECH.2016.2547905.

This paper presents a robust six-degree-of-freedom relative navigation by combining the iterative closet point (ICP) registration algorithm and a noise-adaptive Kalman filter in a closed-loop configuration together with measurements from a laser scanner and an inertial measurement unit (IMU). In this approach, the fine-alignment phase of the registration is integrated with the filter innovation step for estimation correction, while the filter estimate propagation provides the coarse alignment needed to find the corresponding points at the beginning of ICP iteration cycle. The convergence of the ICP point matching is monitored by a fault-detection logic, and the covariance associated with the ICP alignment error is estimated by a recursive algorithm. This ICP enhancement has proven to improve robustness and accuracy of the pose-tracking performance and to automatically recover correct alignment whenever the tracking is lost. The Kalman filter estimator is designed so as to identify the required parameters such as IMU biases and location of the spacecraft center of mass. The robustness and accuracy of the relative navigation algorithm is demonstrated through a hardware-in-the loop simulation setting, in which actual vision data for the relative navigation are generated by a laser range finder scanning a spacecraft mockup attached to a robotic motion simulator.