A Robust Obstacle Avoidance for Service Robot Using Bayesian Approach

Abstract

The objective of this paper is to propose a robust obstacle avoidance method for service robot in indoor environment. The method for obstacles avoidance uses information about static obstacles on the landmark using edge detection. Speed and direction of people that walks as moving obstacle obtained by single camera using tracking and recognition system and distance measurement using 3 ultrasonic sensors. A new geometrical model and maneuvering method for moving obstacle avoidance introduced and combined with Bayesian approach for state estimation. The obstacle avoidance problem is formulated using decision theory, prior and posterior distribution and loss function to determine an optimal response based on inaccurate sensor data. Algorithms for moving obstacles avoidance method proposed and experiment results implemented to service robot also presented. Various experiments show that our proposed method very fast, robust and successfully implemented to service robot called Srikandi II that equipped with 4 DOF arm robot developed in our laboratory.

Keywords

obstacles avoidance service robot moving obstacle bayesian navigation

1. Introduction

Service robot will become an important part of our everyday lives. A typical application is a service robot that should recognizes people and obstacles in indoor/outdoor environment and accomplishes a specific task given by a user. Navigation and moving obstacles avoidance in dynamic and real-world environments for service robot is a complex and challenging task. The robot should maneuvers to avoid obstacles and also reach the goal in an optimal manner. This will lead to demand for robust algorithm for localization, collision free detection and autonomy of service robot (Qing-Xiao Y. et al., 2010; Borenstein J. et al., 1991; Cuesta F., 2005).

During the recent years, many techniques has been developed in order to carry out efficient robot obstacles avoidance using recent sensor data (Masehian E. et al., 2007; Oka F. et al, 2003). General obstacle avoidance can be accomplished with several sensors including vision, sonar, or laser. Potential Field Method (PFM) and Virtual Force Histogram (VFH) for obstacle avoidance have gained increased popularity in the field of mobile robots (Chatib O., 1986; Borenstein J., 1991). PFM is an attractive approach to collision avoidance because of its simplicity and efficient implementation. However, the complexity of tasks that can be implemented using the approach is limited and inherent limitations such as no passage between closely spaced obstacles, oscillations in the presence of obstacles and in narrow passages.

In a cluttered environment, the robot may become trapped at local minima in the resultant potential field, these occur when the attractive forces of the goal are balanced by the repulsive forces due to the presence of obstacles. VFH also have shortcoming that the result is sensitive to threshold and expensive hardware because using histogram grid world model that is updated by rapidly firing 24 sensors around the robot during motion (Borenstein J., 1991). Another drawbacks is PFM and VFH didn't provide complete mechanism for vision based obstacles avoidance and maneuvering for service robot. Obstacle avoidance methods based on ultrasonic sensors must account for the sensor's shortcomings, such as inaccuracies, crosstalk, and spurious readings, so combination of vision and ultrasonic sensors for this research considered, because they are important sensors for face recognition and tracking system and distance measurement for vision-based service robot.

The main challenge for development of service robot is to accurately detect moving obstacles in the landmark. Moving entities must be identified and their future position needs to be predicted over a finite time (Lidoris G. et al., 2008). Due to sensor limitations, the robot can observer only small part of its environment and these observations are corrupted by noise. By integrating successive observations, a map can be created, but since the motion of the robot is subject to error, the mapping problem also comprises a localization problem.

The system for mobile robot to detects moving obstacles in order to gradually stop the robot to avoid collision without maneuvering around obstacle already proposed in (Li Y., et al, 2005), the system uses polar mapping to simplify the segmentation of the moving object from the background. Predictive control of robot velocity to avoid obstacles in a dynamic environments using Hierarchical Partially Observable Markov Decision Process (POMDP) proposed in (Oka F., et al., 2003), in this method, the robot can choose to move at three different speeds: slow, normal and fast.

Bayesian techniques provide a powerful statistical tool to help manage measurement uncertainty and perform multisensor fusion and identity estimation. The advantages of probabilistic robotics are able to accommodate imperfect sensors, robust in real world applications and best known approach to many hard robotics problem. Using sensory information to locate the robot in its environment is the most fundamental problem to providing a service robot with autonomous capabilities (Thrun S., 2006).

Based on literatures obtained by the authors, many research in development of service robot such as (Acosta L. et al., 2006 and Qing-Xiao Y. et al., 2010) that providing basic service such as ordering, fetching and sending food, settlement and so on for customers in the robot restaurant. But there is no flexible and robust obstacles avoidance and maneuvering method for service robot in indoor environment exposed. In previous paper, we already proposed a novel method for static and moving obstacles avoidance for vision-based service robot, but it was using predefined maneuver (Budiharto W. et al, 2010).

The contribution of this paper is the introduction of a new method for navigating and maneuvering to avoids moving obstacle that very fast and suitable for service robot in indoor environment. Bayesian decision theory proposed to determine the optimal response for the robot based on inaccurate sensor data. Our system consist of a single camera which obtains frontal view for object tracking and recognition system and static obstacle detection, compass and 3 ultrasonic sensors for distance measurement. The system easy to be reconfigured if the environment changed. This is presented in Section 2 and 3. Finally, results from the implementation of the proposed method and algorithms on the service robot Srikandi II, that is depicted in Fig 1, are presented in section 4.

Figure 1.

Vision-based service robot called Srikandi II developed and used in this research equipped with 4 DOF arm robot. The camera has a 640×480 pixel resolution. Compass sensor, 3 ultrasonic sensors used as additional sensor for distance measurement and Laptop for image processing (Budiharto, W. et al., 2010).

2. Kinematics Of Wheeled Service Robot

We developed a vision-based service robot called Srikandi II that able to avoid static and moving obstacles, this wheeled robot is next generation from Srikandi I (Budiharto. W. et al, 2010). A mobile robot involving two actuator wheels is considered as a system subject to nonholonomic constraints. Consider an autonomous wheeled mobile robot and position in the Cartesian frame of coordinates shown in fig. 2, where x_R and y_R are the two coordinates of the origin P of the moving frame and θ_R is the robot orientation angle with respect to the positive x-axis. The rotation angle of the right and left wheel denoted as φ_r and φ_l and radius of the wheel by R. The kinematics equations of motion for the robot given by:

{\dot{x}}_{R} = v_{R} \cos θ_{R}

(1)

{\dot{y}}_{R} = v_{R} \sin θ_{R}

(2)

{\dot{θ}}_{R} = ω_{R}

(3)

Figure 2.

Proposed Cartesian representation of robot, moving obstacle and goal.

v_R is the linear velocity, ω_R is the angular velocity, r_R and Λ_R are radial and angular coordinate of the robot. The angular velocity of the right and left wheel can be obtained by:

ω_{r} = \frac{d φ_{r}}{d t} and ω_{l} = \frac{d φ_{l}}{d t}

(4)

Finally, the linear velocity v_R can be formulated as:

v_{R} = R (ω_{r} + ω_{l}) / 2

(5)

Camera as a vision sensor have limitation in angle area for capturing object. We defined θ_Cam as a maximum angle that moving obstacle can be detected by camera used in this research. Based on the fig. 2, we defined angle between moving obstacle and robot θ_{MO_R} as:

θ_{M O_R} = 180^{\circ} - (θ_{R} + θ_{c a m})

(6)

θ_MO,θ_{MO_R},θ_Cam,θ_R, v_R and v_MO are very important properties for calculating whether robot will collides or not with moving obstacle (MO). We proposed mechanism for predicting collision using time t needed for robot to collides the moving obstacle that move with orientation θ_MO as shown in fig. 2 can be calculated by formula:

t = \frac{d_{M O} \sin θ_{M O - R}}{(v_{R} \sin θ_{R} + v_{M O} \sin θ_{M O})}

(7)

We using recursive Bayes decision rule and loss function for deciding the best action for robot (manuevering or stop) that will be described in detail in section 3.2. The speed of moving obstacle v_MO based on vision is a complex task, we propose the model for calculate the v_MO that moving with angle θ_MO detected by the camera, whereas at the same time the robot moving with speed v_R to the goal with angle θ_R, we need 2 point of tracked images with interval t = 1 second, then the difference of pixel position obtained.

Fig. 3 shown below is an architecture of service robot Srikandi II that utilizing single camera, compass and distance sensors. Because this robot need to recognizes and tracks people, many supporting functions developed and integrated such as face recognition system, static and moving obstacles detection, moving obstacle tracking and Bayesian Filtering, to make the robot robust and reliable. We developed efficient Faces database used by Face recognition system for recognizing customer. There is interface program between Laptop for coordinating robot controller. 4 DOF arm robot with predefined motion used for giving a cup to customer when robot arrived at goal position. 1 master controller used for coordinating actuator and communication with the laptop and another controller used dedicated for distance measurement. In our previous research, Srikandi II implements path planning for the shortest path based on using Dijkstra algorithm(Dijkstra, 1959).

Figure 3.

General architecture of service robot Srikandi II. Hardware and software parts are separated by the dashed line. All arrows indicate dataflow.

3. Proposed Method

3.1. Moving obstacle avoidance Method

In this paper, we proposed a new method for maneuvering robot whereas the robot detects static and moving obstacle and predicts that collision will occurred as shown in fig. 4. This method is combination of static and moving obstacles detection using vision and ultrasonic sensors. Information about static obstacle obtained when robot start to running. Images from the landmark captured and stored in .jpg file and program will scanning the images for find the free area used by robot for running. At the end of program, the path from start to goal position obtained. The next step is detection and face recognition to identify the customer. Moving obstacle information obtained when robot detects and tracks the people walks in front of robot periodically every 500ms and distance of moving obstacle obtained using 3 ultrasonic sensors periodically every 100ms.

Figure 4.

Flow chart of obstacles avoidance and state estimation of moving obstacle using Bayesian decision rule for service robot from start to goal position.

We introduces a new geometrical model for moving obstacle avoidance. The proposed model for maneuvering moving obstacle shown in our model in fig. 5 below:

Figure 5.

Model of maneuvering method for moving obstacle avoidance. This show that robot maneuvers to avoids collision with moving obstacle smoothly based on calculation of direction, velocity and distance between robot and moving obstacle.

The constant of collision angle denoted as k_θ and the minimum distance to start maneuvering denoted as d_safe, when robot detecting that the minimum distance to start maneuvering reached, the turning angle to avoid collision θ_m is:

θ_{m} = θ_{R} + (\frac{π}{2} (k_{θ} / d_{M O})) if d_{M O} < d_{s a f e}

(8)

And if d_n as the minimum distance to reorientation the robot to the goal reached, the turning angle is:

θ_{m} = θ_{R} if d_{s a f e} > d_{M O} > d_{n}

(9)

If d_safe > d_MO > d_n reached, then robot start to reorientation to the goal using compass sensor based on data obtained before. The velocity of the robot v_R when in the avoidance mode is configured between v_max/2 - v_max, and the maximal speed occurred when Δθ_m is π/2, the proposed formula is:

v_{R = v_{\max} (1 - | 0.5 - \frac{Δ θ_{m}}{π} |)}

(10)

3.2. State Estimation using Bayesian

Bayesian decision rule probabilistically estimate a dynamic system state from noisy observations. Bayes filters represent the state at time t by random variable x_t. Within the Bayesian framework, a probability density of an object's state x ∈ S is maintained conditioned on the observations z (sensor measurements) obtained. Examples of measurement data include camera images and range scan. If x is a quantity that we would like to infer from y, the probability p(x) will be referred to as prior probability distribution. The Bayesian update formula is applied to determine the new posterior p(x,y) whenever a new observation is obtained:

p (x, y) = \frac{p (y | x, z) p (x | z)}{p (y | z)}

(11)

At each point in time, a probability distribution over x_t called belief and denoted bel(x_t), it represents the uncertainty. A belief reflects the robot's internal knowledge about the state of the environment. Probabilistic robotics represents belief through conditional probability distributions. A belief distribution assigns a probability to each possible hypothesis with regards to the true state. The sensor data consist of a sequence of time-indexed sensor observations z=[z₁,z₂,…,z_t]^T. The belief bel(x_t) is then defined by the posterior density over the random variable x_t conditioned on all sensor data available at time t:

b e l (x_{t}) = p (x_{t} | z_{1 : t}, u_{1 : t})

(12)

= η p (z_{t} | x_{t}) \bar{b e l} (x_{t})

(13)

This posterior is the probability distribution over the state x_t at time t, conditioned on all past measurements z_t and al past controller u_1:t. In mobile robot, a typical example of control data is the velocity of a robot. η is a normalizer in Bayes rule variable. To calculate a posterior before incorporating z_t just after executing the control u_t:

\bar{b e l} (x_{t}) = p (x_{t} | z_{1 : t - 1,} u_{1 : t})

(14)

= \int p (x_{t} | u_{t,} x_{t - 1}) b e l (x_{t - 1}) d x_{t - 1}

(15)

= \sum_{x_{t - 1}} p (x_{t} | u_{t}, x_{t - 1}) b e l (x_{t - 1})

(16)

This probability distribution is often referred to as prediction in the context of probabilistic filtering (Thrun S., 2006). To apply Bayesian decision theory for obstacle avoidance, we consider the appearance of an unexpected obstacle to be a random event. The probabilistic information in z about θ is described by a conditional probability density function p(z | θ) of the observation vector z, we called as the likelihood function. Let θ denote the state of the path to be a random variable consisting of two states:

Θ = (θ_{1}, θ_{2})

(17)

(o b s t a c l e, n o_o b s t a c l e)

(18)

If we want service robot should stay on the path in any case, strategies to avoid moving obstacle include:

Maneuver, if service robot will collides.

stop, if moving obstacle too close to robot.

Then, we restrict the action space denoted as A as:

Α = (a_{1,} a_{2})

(19)

= (m a n e u v e r, s t o p)

(20)

We define a loss function L(θ, a) which gives a measure of the loss incurred in taking action a when the state is θ. The robot should chooses an action a from the set A of possible actions based on the observation z of the current state of the path θ. This gives the posterior distribution of θ as:

p (θ | z) = \frac{p (z | θ) p (θ)}{\sum p (z | θ) p (θ)}

(21)

Then, based on the posterior distribution in (21), we can compute the posterior expected loss of an action (Hu. H et al., 1994):

B (p (θ | z), a) = \sum_{θ} L (θ, a) p (θ | z)

(22)

For implementing the above method, we proposed algorithm obstacles avoidance for service robot that run from start to goal position, giving a cup to customer and going back to home as shown below.

Algorithm 1. Algorithm for robust obstacles avoidance and for service robot.

Capture and saving landmark Call staticObstacleDetection //Using CANNY edge detector Face identification // Face recognition system if (customer_detected ==true) then do while not goal Set heading robot to the goal Call movingObstacleDetectionTracking Robot running with normal speed if (moving_obstacle==true) then Tracking moving obstacle and calculate speed Distance measurement of moving object State estimation of moving obstacle using Bayesian if (min_distance d_safe ==true and collision==true) then // maneuvering robot Adjust turning angle and speed Update position of robot to the goal position endif else Move to goal position endif Move to goal position Giving a cup to customer and go to home/ start position else Robot stop // if no customer detected endif function staticObstacleDetection capture Landmark and static obstacle processing end function function movingObstacleDetectionTracking Moving obstacle detection and tracking end function

4. Experimental Results and Discussion

Experiments of obstacle avoidance has been tested for navigating service robot to delivers a cup in our lab. 4×5meters as a simulation of indoor environment. Face tracking and recognition based on eigenspaces with 3 images per person used and databases for the images have been developed (Budiharto, W., 2010). For maneuvering the robot, we setup the experiment to ensure that moving obstacle will collides with robot, we use parameters shown in Table 1:

Table 1.

Variables used in our experiments.

No	Variables	Values
1	θ_MO	0° − 30°
2	v _MO	0.15–0.3 m/s
3	v _R	0.15 – 0.3m/s
4	θ_Cam	30°
5	d _safe	120 cm
6	d _n	90 cm

The procedure of experiment can be described here. First, robot will capture the landmark and processing the images to obtain static obstacles and start-goal position as shown in fig. 6, then robot will detects if the customer available or no, if the customer exist, program will detects and tracking moving obstacles. We use upper body features for moving obstacles detection from OpenCV library, frontal face features used for customer's detection and camshift method for tracking. Robot continuously measures the distance of obstacle and send the data to Laptop. Because the limitation of area, people as moving obstacle only walk straight in front of robot and approach to robot. The speed of robot limited to 3 condition, low speed is 0.1 m/s, normal speed is equal to 0.2m/s and fast is equal to 0.3 m/s.

Figure 6.

Result of simulation for service robot for detecting static obstacles using CANNY edge detection and path planning from start to goal position. Line from start to goal as a guidance for robot to moves.

For estimating the direction of moving obstacles, we use tracking and motion history method as shown in fig. 7. These methods better than optical flow method that very sensitive and difficult to calculating the speed.

Figure 7.

Detecting and tracking moving obstacle and direction identification of movement (a) and motion history with the direction of movement in red line indicated that the people walk approach to robot (b).

If there is was no moving obstacle, robot run from start to goal position in normal speed. If moving obstacle appeared and collision will occurred, robot will maneuver to avoids obstacle, and the turning angle and speed varied based on Eq. 8 –10. To calculate the Bayes decision, suppose:

p (z | θ_{1}) = 0.7 and p (z | θ_{2}) = 0.3

(23)

where p(z|(θ₁)is the measure of how likely a state of nature is θ₁ given the observation z, and p(z|(θ₂) is a measure of how likely the state is θ₂ given the observation z. Suppose we have a prior distribution of the state θ for path:

p (θ_{1}) = 0.8 and p (θ_{2}) = 0.2

(24)

Then, we calculate the posterior distribution :

p (θ_{1} | z) = \frac{p (z | θ_{1}) p (θ_{1})}{\sum_{i = 1}^{2} p (z | θ_{i}) p (θ_{i})}

(25)

\begin{matrix} = \frac{0.7 \times 0.8}{0.7 \times 0.8 + 0.3 x 0.2} \\ = 0.907 \end{matrix}

(26)

p (θ_{2} | z) = \frac{p (z | θ_{2}) p (θ_{2})}{\sum_{i = 1}^{2} p (z | θ_{i}) p (θ_{i})}

(27)

\begin{matrix} = \frac{0.3 \times 0.2}{0.7 \times 0.8 + 0.3 \times 0.2} \\ = 0.019 \end{matrix}

(28)

Then, we calculate the posterior expected loss for a₁ and a₂. L(θ₁, a₁) is the loss incurred by taking the action a₁ (maneuver) given that the path is passable, θ = θ₁. The loss L(θ₂,a₁) is incurred by the maneuver action when the true state of the path is no obstacle, we set as 5 seconds. L(θ₁, a₂) is the loss incurred by stopping robot for 5 seconds when the path is in fact there is a moving obstacle. We define it to be zero since the robot incurred no loss. The loss L(θ₂,a₂) is incurred by the stop action when the true state of the path is no obstacle and we set doubled loss as 10 second, the result shown in table 2 below:

Table 2.

Definition of loss function

Action	θ₁ (obstacle)	θ₂ (no_obstacle)
a₁ (maneuver)	0	5
a₂ (stop)	5	10

\begin{matrix} B (p (θ | z), a_{1}) = \sum_{i = 1}^{2} L (θ_{i}, a_{1}) p (θ_{i} | z) \\ = 0 \times 0.907 + 5 \times 0.019 \\ = 0.095 \end{matrix}

(29)

\begin{matrix} B (p (θ | z), a_{2}) = \sum_{i = 1}^{2} L (θ_{i}, a_{2}) p (θ_{i} | z) \\ 5 \times 0.907 + 10 \times 0.019 \\ = 4.725 \end{matrix}

(30)

Based on (29) and (30), we see that a₁ has the smaller expected loss, therefore the robot should chooses the maneuver action to avoid the moving obstacle.

Figure shown below is result of static and moving obstacle avoidance and maneuvering for service robot in our experiments.

Figure 8.

Result of experiment for obstacle avoidance for service robot. It shown that robot succesfully avoids static and moving obstacle while reaching the goal position.

In general, the proposed method has been successfully implemented and shows good performance. 3 ultrasonic sensors satisfied to detect and measure the distance of moving obstacle continuously. Noise or imperfect distance measurement still give expected action for robot to maneuver smoothly. As indication of the fast performance of our method and algorithm is the sampling time T (i.e the rate at which the steer and speed commands for the low cost controller are issued. The following steps occur during T:

Obtain 3 sonar information from the sensor controller

Calculating the moving obstacle distance

Calculate the speed command

Determine the action

Communicate with the motion controller for send speed and steer command.

On Laptop Intel Atom 1.6 GHz and 1 GB RAM, T =220 ms.

5. Conclusion

This paper presents a robust obstacles avoidance method for service robot in indoor environment. Geometrical model for moving obstacle avoidance and algorithms for static and moving obstacle proposed then implemented to service robot. Integration of vision and ultrasonic sensors proved applicable as main sensors for service robot. Experimental results with various situations have shown that the robot reaches the goal points while avoiding moving obstacle with the proposed method, and does not have limitation of improving the complexity the system as the changes of environment. The Strength of the maneuvering method proposed shown good performance for moving obstacle avoidance. Bayesian decision rule implemented for state estimation makes this method more robust because the optimal solution for avoiding obstacles is obtained by trading between maneuver and stop action. Our future work will focus on the navigation system and arm capabilities for giving a cup to customer using stereo vision.

References

Qing-Xiao

Can

Zhuang

, and Zheng

(2010). Research of the Localization of Restaurant Service Robot, International Journal of Advanced Robotic Systems, vol. 7 no.3, pp. 227–238, ISSN: 1729-8806, InTech.

Borenstein

Koren

(1991). The Vector Field Histogram- Fast Obstacle Avoidance for Mobile Robots, in proc. IEEE Trans. On Robotics and Automation, vol 7 (3), pp.278–288.

Cuesta

Ollero

, Intelligent Mobile Robot Navigation (2005), Springer, pp. 10–25.

Masehian

Katebi

(2007). Robot Motion Planning in Dynamic Environments with Moving Obstacles and Target, Int. Journal of Mechanical Systems Science and Engineering, 1 (1), pp. 20–25.

and He

(2005). A Novel Obstacle Avoidance and Navigation Method of Outdoor Mobile Robot, in proc. 12th International conf. on Advanced Robotics, pp.653–656.

Oka

and Trahanias

(2003). Predictive Control of Robot Velocity to Avoid Obstacles in Dynamic Environments, International conf. on Intelligent robots and systems, Nevada, pp. 370–375.

Khatib

(1986) Real-time Obstacle Avoidance for Manipulator and Mobile Robots, International Journal of Robotics Research 5 (1), pp.90–98.

Borenstein

and Koren

(1991). Potential Field Methods and Their Inherent Limitations for Mobile Robot Navigation, in proc. IEEE Conf. on Robotics and Automation, Californnia, pp.1398–1404.

Lidoris

Wollherr

and Buss

(2008) Bayesian State Estimation and Behavior Selection for Autonomous Robot Exploration in Dynamic Environments, IEEE International conf. on Intelligent robots and systems, France.

10.

Thrun

, Probabilistic Robotics (2006), The MIT Press, pp. 10–30.

11.

Dijkstra

E.W.

(1959), A Note on Two Problems in Connection with Graphs, Numer. Math 1, pp. 269–271.

12.

Budiharto

Purwanto

and Jazidie

(2010), A Novel Method for Static and Moving Obstacle Avoidance for Service robot using Bayesian Filtering, IEEE 2nd International conf. on Advances in Computing, Control and Telecommunications Technology, Jakarta-Indonesia, pp. 156–160. DOI: 10.1109/ACT.2010.51.

13.

Budiharto

Purwanto

and Jazidie

(2010). Indoor Navigation using ANFIS controller for Servant Robot, in proc. IEEE 2nd International Conference on Computer Engineering and Its Application (ICCEA 2010), Bali-Indonesia, pp. 582. 586. DOI: 10.1109/ICCEA.2010.119.

14.

and Brady

(1994). A Bayesian Approach to Real-Time Obstacle Avoidance for a Mobile Robot. Autonomous Robots, vol. 1, Kluwer Academic Publishers, Boston, pp. 69–92.

15.

Acosta

González

E.J.

Rodríguez

J.N.

Hamilton

A.F.

(2006), Design and Implementation of a Service Robot for A Restaurant, International Journal of robotics and automation, vol. 21 no.4, pp. 273–281.