Presentation Peshala

Robust Sensor-Based Navigation for Mobile Robots

Peshala G Jayasekara, M1

IEEE TRANSACTIONS ON INSTRUMENTATION AND MEASUREMENT, VOL. 58, NO. 3, MARCH 2009

Immanuel A. R. Ashokaraj, Peter M. G. Silson, Antonios Tsourdos, Member, IEEE, and Brian A. White

Outline • • • • • • • • •

Motivation Introduction Interval Analysis Approach Map Algorithms Localization Results Conclusion – Evaluation and Opinion

Motivation • A deterministic approach for sensor-based localization and navigation of a mobile robot • Try to avoid computational complexity and linearity found in classical methods such as Kalman Filter • The interval analysis method proposed in this paper bypasses the data-association step and directly deals with the nonlinear problem in a global way

Introduction • Addresses the problem of localization of a fourwheeled mobile robot with ultrasonic sensors using “Interval Analysis”

• Map of the environment is available - priori

Interval Analysis (I) • Interval analysis is based on the set theory and gives a guaranteed approximation of the set of all the actual solutions of the problem being considered • Defines operations on intervals rather than individual numbers • Interval Arithmetic even span vectors, matrices

Interval Analysis (II) • Basic Definitions and Notations • Addition, subtraction, multiplication, division

The basic operations of interval arithmetic are, for two intervals [a, b] and [c, d] that are subsets of the real line (-∞, ∞), [a,b] + [c,d] = [a + c, b + d] [a,b] - [c, d] = [a - d, b - c] [a,b] x [c,d] = [min (ac, ad, bc, bd), max (ac, ad, bc, bd)] [a,b] / [c,d] = [min (a/c, a/d, b/c, b/d), max (a/c, a/d, b/c, b/d)]

• Example

Interval Analysis (III) • Essential Operations – Computing an interval that contains the image of [x] using f obtained due to the notion of inclusion function

– The notion of inclusion test that tests whether [x] belongs to S or not – The contraction of [x] w.r.t S

Approach (I) • The problem is to estimate the vector p = (xc, yc , θ) from – a map representing the environment of the robot and – from the distance measurements provided by a belt of ns ultrasonic sensors present in the mobile robot

• When the bounds on the measurement error are known, – then the resulting distance measurement in terms of the intervals stored in an interval vector is given by

Approach (II) •

If a model of the ultrasonic sensor interval distance measurements represented by interval vector dm(p) when the robot configuration p is available, then the robot localization problem becomes a bounded error parameter estimation problem, particularly that characterizing the set

•

Since the task is to find p – for a given configuration vector p, the robot evaluates the measurements that its sensors return and compares them with the actual measurements to check whether they are consistent

•

The described problem can then be solved using one of two approaches: – set inversion via interval analysis (SIVIA) – image subpaving (ImageSP).

Map (I) • Definition – The map M = {[aj, bj ]|j = 1, . . . , nw} of the robot’s environment is assumed to consist of nw oriented segments with extremes [aj, bj ] that describe the obstacles and all the landmarks. – By convention, when going from aj to bj , the reflecting face of the segment is on the left

Map (II) • Measurement Process Model – For any given sensor i and configuration vector p, the distance that would be obtained if only one segment of the map were present is computed. – This is then repeated for all the segments in the map. The final distance taken as the ith sensor reading (remoteness) will be the smallest of the distances computed for all the segments of the map

Algorithms

Localization (I) • To check whether a given state x is consistent with the measured outputs {[di]}ns i=1, – the robot evaluates the measurements that its sensors would return if it were in the state x and compares them with the actual measurements. – The test t(x) must hold true if and only if they are deemed compatible

• The state x is consistent with all measurements (and thus t(x) = 1) – if all ri's (remoteness) are consistent with the map

Localization (II) • SIVIA – Set Inversion Via Interval Analysis

– if t[]([po]) = 1, then po is in the solution set P and is stored – If t[]([po]) = 0, then [po] has an empty intersection with P and is dropped from further consideration – If t[]([po]) = [0, 1] and the width of [po] is larger than the pre-specified precision parameter ε, then po is bisected, leading to two child subboxes L(p) and R(p), and test t[](.) is recursively applied to both of them. Any box with a width smaller than ε is considered to be small enough and is added to P. – This algorithm is finite, and its complexity has been studied

• ImageSP Evaluation Procedure – When f is not invertible

Localization (III) • Once the robot knows its position at any given instant of time, it can use this information to narrow down the initial configuration vector [po] to reduce the computational time – Use the physical limitations of the robot to predict [po]

Results (I) • SIVIA Algorithm

Results (II) • ImageSP Algorithm

Conclusion • A basic introduction to interval analysis and its application to the problem of robot localization • The localization procedure used here for tracking the mobile robot does not suffer from the same disadvantages of commonly used localization procedures such as EKF • As the next step, the authors want to incorporate sensor fusion

Evaluation and Opinion • Authors have tried a different approach rather than sticking into Kalman filter • We can try using this method for laser range finder instead of ultrasonic sensors • At the presence of dynamic obstacles, suitability of this algorithm is not very clear

Thank you

Questions??