Category Archives: Robotics

Using the Bingham distribution of probability, which is defined on a d-dimensional sphere to be antipodally symmetric, to address the problem of angle periodicity in [0,2pi] when estimating orientation in a recursive filter

February 4, 2016 16:44 ,

Gilitschenski, I.; Kurz, G.; Julier, S.J.; Hanebeck, U.D., Unscented Orientation Estimation Based on the Bingham Distribution, in Automatic Control, IEEE Transactions on , vol.61, no.1, pp.172-177, Jan. 2016, DOI: 10.1109/TAC.2015.2423831.

In this work, we develop a recursive filter to estimate orientation in 3D, represented by quaternions, using directional distributions. Many closed-form orientation estimation algorithms are based on traditional nonlinear filtering techniques, such as the extended Kalman filter (EKF) or the unscented Kalman filter (UKF). These approaches assume the uncertainties in the system state and measurements to be Gaussian-distributed. However, Gaussians cannot account for the periodic nature of the manifold of orientations and thus small angular errors have to be assumed and ad hoc fixes must be used. In this work, we develop computationally efficient recursive estimators that use the Bingham distribution. This distribution is defined on the hypersphere and is inherently more suitable for periodic problems. As a result, these algorithms are able to consistently estimate orientation even in the presence of large angular errors. Furthermore, handling of nontrivial system functions is performed using an entirely deterministic method which avoids any random sampling. A scheme reminiscent of the UKF is proposed for the nonlinear manifold of orientations. It is the first deterministic sampling scheme that truly reflects the nonlinear manifold of orientations.

Posted in: Bayesian filtering, Mobile Robot Localization , Tagged: ,

Robotic probabilistic SLAM in continuous time

December 22, 2015 19:43 ,

Furgale1 P., Tong C.-H., Barfoot T.-D., Sibley G., Continuous-time batch trajectory estimation using temporal basis functions, The International Journal of Robotics Research December 2015 vol. 34 no. 14 1688-1710, DOI: 10.1177/0278364915585860.

Roboticists often formulate estimation problems in discrete time for the practical reason of keeping the state size tractable; however, the discrete-time approach does not scale well for use with high-rate sensors, such as inertial measurement units, rolling-shutter cameras, or sweeping laser imaging sensors. The difficulty lies in the fact that a pose variable is typically included for every time at which a measurement is acquired, rendering the dimension of the state impractically large for large numbers of measurements. This issue is exacerbated for the simultaneous localization and mapping problem, which further augments the state to include landmark variables. To address this tractability issue, we propose to move the full Maximum-a-Posteriori estimation problem into continuous time and use temporal basis functions to keep the state size manageable. We present a full probabilistic derivation of the continuous-time estimation problem, derive an estimator based on the assumption that the densities and processes involved are Gaussian and show how the coefficients of a relatively small number of basis functions can form the state to be estimated, making the solution efficient. Our derivation is presented in steps of increasingly specific assumptions, opening the door to the development of other novel continuous-time estimation algorithms through the application of different assumptions at any point. We use the simultaneous localization and mapping problem as our motivation throughout the paper, although the approach is not specific to this application. Results from two experiments are provided to validate the approach: (i) self-calibration involving a camera and a high-rate inertial measurement unit, and (ii) perspective localization with a rolling-shutter camera.

Posted in: Mobile robot SLAM , Tagged:

Model checking for the verification of the correct functionality in the presence of sensor failures of a network of behaviours included in a robotic architecture

December 22, 2015 19:14 ,

Lisa Kiekbusch, Christopher Armbrust, Karsten Berns, Formal verification of behaviour networks including sensor failures, Robotics and Autonomous Systems, Volume 74, Part B, December 2015, Pages 331-339, ISSN 0921-8890, DOI: 10.1016/j.robot.2015.08.002.

The paper deals with the problem of verifying behaviour-based control systems. Although failures in sensor hardware and software can have strong influences on the robot’s operation, they are often neglected in the verification process. Instead, perfect sensing is assumed. Therefore, this paper provides an approach for modelling the sensor chain in a formal way and connecting it to the formal model of the control system. The resulting model can be verified using model checking techniques, which is shown on the examples of the control systems of an autonomous indoor robot and an autonomous off-road robot.

Posted in: Robotic architectures, Robotic software , Tagged: ,

Study of how a complex motion planning problem solved through RRT can benefit from parallelization

November 12, 2015 19:59 ,

Brian W. Satzinger, Chelsea Lau, Marten Byl, Katie Byl, Tractable locomotion planning for RoboSimian, The International Journal of Robotics Research November 2015 vol. 34 no. 13 1541-1558, DOI: 10.1177/0278364915584947.

This paper investigates practical solutions for low-bandwidth, teleoperated mobility for RoboSimian in complex environments. Locomotion planning for this robot is challenging due to kinematic redundancy. We present an end-to-end planning method that exploits a reduced-dimension rapidly-exploring random tree search, constraining a subset of limbs to an inverse kinematics table. Then, we evaluate the performance of this approach through simulations in randomized environments and in the style of the Defense Advanced Research Projects Agency Robotics Challenges terrain both in simulation and with hardware.
We also illustrate the importance of allowing for significant body motion during swing leg motions on extreme terrain and quantify the trade-offs between computation time and execution time, subject to velocity and acceleration limits of the joints. These results lead us to hypothesize that appropriate statistical “investment” of parallel computing resources between competing formulations or flavors of random planning algorithms can improve motion planning performance significantly. Motivated by the need to improve the speed of limbed mobility for the Defense Advanced Research Projects Agency Robotics Challenge, we introduce one formulation of this resource allocation problem as a toy example and discuss advantages and implications of such trajectory planning for tractable locomotion on complex terrain.

Posted in: Robot motion planning , Tagged: ,

Comparison of EKF and UKF for robot localization and a method of selection of a subset of the available sonar sensors

October 5, 2015 09:27 ,

Luigi D’Alfonso, Walter Lucia, Pietro Muraca, Paolo Pugliese, Mobile robot localization via EKF and UKF: A comparison based on real data, Robotics and Autonomous Systems, Volume 74, Part A, December 2015, Pages 122-127, ISSN 0921-8890, DOI: 10.1016/j.robot.2015.07.007.

In this work we compare the performance of two well known filters for nonlinear models, the Extended Kalman Filter and the Unscented Kalman Filter, in estimating the position and orientation of a mobile robot. The two filters fuse the measurements taken by ultrasonic sensors located onboard the robot. The experimental results on real data show a substantial equivalence of the two filters, although in principle the approximating properties of the UKF are much better. A switching sensors activation policy is also devised, which allows to obtain an accurate estimate of the robot state using only a fraction of the available sensors, with a relevant saving of battery power.

Posted in: Mobile Robot Localization , Tagged: , , , ,

One of the first thorough studies of Monte Carlo Localization with line-segment maps

October 5, 2015 09:23 ,

Biswajit Sarkar, Surojit Saha, Prabir K. Pal, A novel method for computation of importance weights in Monte Carlo localization on line segment-based maps, Robotics and Autonomous Systems, Volume 74, Part A, December 2015, Pages 51-65, ISSN 0921-8890, DOI: 10.1016/j.robot.2015.07.001.

Monte Carlo localization is a powerful and popular approach in mobile robot localization. Line segment-based maps provide a compact and scalable representation of indoor environments for mobile robot navigation. But Monte Carlo localization has seldom been studied in the context of line segment-based maps. A key step of the approach–and one that can endow it with or rob it of the attributes of accuracy, robustness and efficiency–is the computation of the so called importance weight associated with each particle. In this paper, we propose a new method for the computation of importance weights on maps represented with line segments, and extensively study its performance in pose tracking. We also compare our method with three other methods reported in the literature and present the results and insights thus gathered. The comparative study, conducted using both simulated and real data, on maps built from real data available in the public domain clearly establish that the proposed method is more accurate, robust and efficient than the other methods.

Posted in: Mobile Robot Localization , Tagged: , ,

Survey on Model-Driven Software Engineering for real-time embedded systems and robotics

October 1, 2015 18:37 ,

Brugali, D., Model-Driven Software Engineering in Robotics: Models Are Designed to Use the Relevant Things, Thereby Reducing the Complexity and Cost in the Field of Robotics, in Robotics & Automation Magazine, IEEE , vol.22, no.3, pp.155-166, Sept. 2015, DOI: 10.1109/MRA.2015.2452201.

A model is an abstract representation of a real system or phenomenon [1]. The idea of a model is to capture important properties of reality and to eglect irrelevant details. The properties that are relevant and that can be neglected depend on the purpose of creating a model. A model can make a particular system or phenomenon easier to understand, quantify, visualize, simulate, or predict.

Posted in: Real-Time Systems, Robotic software , Tagged: , ,

Planning tasks in mobile robots with MDPs that maximize the probability of satisfying user’s requirements specified through temporal logics, with estimation of transition probabilities through simulation only when needed

September 30, 2015 18:53 ,

Jing Wang, Xuchu Ding, Morteza Lahijanian, Ioannis Ch. Paschalidis, and Calin A. Belta, Temporal logic motion control using actor–critic methods, The International Journal of Robotics Research September 2015 34: 1329-1344, first published on May 26, 2015. DOI: 10.1177/0278364915581505.

This paper considers the problem of deploying a robot from a specification given as a temporal logic statement about some properties satisfied by the regions of a large, partitioned environment. We assume that the robot has noisy sensors and actuators and model its motion through the regions of the environment as a Markov decision process (MDP). The robot control problem becomes finding the control policy which maximizes the probability of satisfying the temporal logic task on the MDP. For a large environment, obtaining transition probabilities for each state–action pair, as well as solving the necessary optimization problem for the optimal policy, are computationally intensive. To address these issues, we propose an approximate dynamic programming framework based on a least-squares temporal difference learning method of the actor–critic type. This framework operates on sample paths of the robot and optimizes a randomized control policy with respect to a small set of parameters. The transition probabilities are obtained only when needed. Simulations confirm that convergence of the parameters translates to an approximately optimal policy.

Posted in: Robot task planning , Tagged: , ,

Building probabilistic models of physical processes from their deterministic models and some experimental data, with guarantees on the degree of coincidence between the generated model and the real system

September 30, 2015 18:44 ,

Konstantinos Karydis, Ioannis Poulakakis, Jianxin Sun, and Herbert G. Tanner, Probabilistically valid stochastic extensions of deterministic models for systems with uncertainty, The International Journal of Robotics Research September 2015 34: 1278-1295, first published on May 28, 2015. DOI: 10.1177/0278364915576336.

Models capable of capturing and reproducing the variability observed in experimental trials can be valuable for planning and control in the presence of uncertainty. This paper reports on a new data-driven methodology that extends deterministic models to a stochastic regime and offers probabilistic guarantees of model fidelity. From an acceptable deterministic model, a stochastic one is generated, capable of capturing and reproducing uncertain system–environment interactions at given levels of fidelity. The reported approach combines methodological elements from probabilistic model validation and randomized algorithms, to simultaneously quantify the fidelity of a model and tune the distribution of random parameters in the corresponding stochastic extension, in order to reproduce the variability observed experimentally in the physical process of interest. The approach can be applied to an array of physical processes, the models of which may come in different forms, including differential equations; we demonstrate this point by considering examples from the areas of miniature legged robots and aerial vehicles.

Posted in: Probability and statistics, Robot models , Tagged:

Nice related work on efficient POMDPs and two novel approaches to reduce their computational cost

September 28, 2015 12:18 ,

Grady, D.K.; Moll, M.; Kavraki, L.E., Extending the Applicability of POMDP Solutions to Robotic Tasks, in Robotics, IEEE Transactions on , vol.31, no.4, pp.948-961, Aug. 2015 DOI: 10.1109/TRO.2015.2441511

Partially observable Markov decision processes (POMDPs) are used in many robotic task classes from soccer to household chores. Determining an approximately optimal action policy for POMDPs is PSPACE-complete, and the exponential growth of computation time prohibits solving large tasks. This paper describes two techniques to extend the range of robotic tasks that can be solved using a POMDP. Our first technique reduces the motion constraints of a robot and, then, uses state-of-the-art robotic motion planning techniques to respect the true motion constraints at runtime. We then propose a novel task decomposition that can be applied to some indoor robotic tasks. This decomposition transforms a long time horizon task into a set of shorter tasks. We empirically demonstrate the performance gain provided by these two techniques through simulated execution in a variety of environments. Comparing a direct formulation of a POMDP to solving our proposed reductions, we conclude that the techniques proposed in this paper can provide significant enhancement to current POMDP solution techniques, extending the POMDP instances that can be solved to include large continuous-state robotic tasks.

Posted in: Robot task planning , Tagged: ,