Motion Planning for Mobile Robots Using a Spline Surface

(1)

1. INTRODUCTION

A mobile robot needs to decide a path toward a target avoiding encountered obstacles in a given space using a motion plan. There are some methods of motion planning such as graph search, cell division, road map, and artificial potential methods [1]. The artificial potential method uses a potential field, to guide a robot from start to goal configurations. The potential field consists of attractive potential used to pull a robot toward a goal and repulsive potential to keep it away from obstacles.

An artificial potential method includes Khatib’s Method [2], while the method of Laplace’s differential equation [3] and so on have been proposed as an artificial potential method. Khatib’s method sets an attractive potential based on the distance between current and target points and sets a repulsive potential based on the nearest distance between a current point and an obstacle. Since the potential field is not generated in consideration of all obstacles in an environment, the method tends to cause a problem of local minimum. As some methods have been developed such as that using random walks to resolve the problem [4], a potential field without a local minimum is desirable for motion planning.

The method using a Laplace differential equation is a method used to generate a potential field without a local minimum. The method generates a potential field by solving a Laplace differential equation and utilizing it for motion planning. Since the method is time consuming, it is difficult to change a potential field in real-time according to environmental changes.

Although Rimon’s method [5] and that using fluid potential [6] also provide a potential field without a local minimum, they are only applicable to simple boundary figures and not to the arbitrary figures of boundaries.

This study proposes a method to utilize a spline function that interpolates arbitrary boundaries and a domain reduction method that reduces the unnecessary area୊Chapter 2 describes the fundamental algorithm of the proposed method. Chapter 3 describes a method to generate artificial potential

for a two-dimensional problem. Chapter 4 shows a domain reduction method to resolve the problem of local minimum. Chapter 5 introduces a method to avoid a moving obstacle. Chapter 6 shows the simulation results, before finally, chapter 7 draws a conclusion.

Motion Planning for Mobile Robots Using a Spline Surface

Kiyotaka Kato, Jyunichi Tanaka, and Hironori Tokunaga

* * Department of Electrical Engineering, Tokyo University of Science, Tokyo, Japan

(Tel : +81-3-5228-8330; E-mail: [email protected])

Abstract: The artificial potential method uses a potential field to guide a robot from a startto a goal configuration respectively. The potential field consists of attractive potential used to pull a robot toward a goal and repulsive potential to keep it away from obstacles. However, there are two problems concerning local minimum and computational cost to be resolved in conventional artificial potential methods. This study proposes a method utilizing a spline surface that interpolates arbitrary boundaries and a domain reduction method that reduces the unnecessary area. The proposed spline surface interpolates arbitrary shaped boundaries and is used as an artificial potential to guide a robot for global motion planning of a mobile robot. A reduced domain process reduces the unnecessary domain. We apply a distance-weighted function as such a function, which blends distances from each boundary with a reduction in computational time compared with other analytical methods. As a result, this paper shows that an arbitrary boundary spline surface provides global planning and a domain reduction method reduces local minimum with quick operation.

Keywords:artificial potential method, robot, motion planning, collision avoidance

2. MOTION PLANNING FOR MOBILE

ROBOT USING A SPLINE SURFACE

Let CS be the configuration space for a mobile robot. Then, let FS be a free space within the configuration space CS, where a robot can move without any collision. Let ȍ be a boundary of the free space FS. Here, CS and FS are n-dimensional space and ȍ is an (n-1)-dimensional space. And define start and goal configurations respectively in the free space FS. There, suppose the FS is a continuous space, namely, that there is a path between the start and goal configurations. Moreover, a domain D is prepared so that it may be mapped on the free space FS using a spline surface. Let S and G be start and goal points respectively in the domain D. S and G are therefore mapped to the start configuration and goal configurations respectively.

The purpose is to find a path that guides a robot from the start to goal configurations in the FS, that is, from the start point S to the goal point G in the domain D. To realize this, the following processes are repeatedly performed.

(1) Path generation process

The process generates a path along which a robot moves effectively between the current and target positions. If the current domain contains current and goal points respectively, it is guaranteed that there is a path to guide a robot toward the goal. The process within a reduced domain uses a spline function as an evaluation function. We apply a distance-weighted function for this purpose, which blends distances from each boundary with a reduction in computational time compared with other analytical methods.

(2) Domain reduction process

This process divides and reduces unnecessary parts from global consideration so that a robot moves to the goal

(2)

The following chapter describes a concrete method of application to a two-dimensional problem.

configuration.

In spite of the global perspective, there are cases when a robot cannot reach a target. In this case, the domain reduction method is applied to resolve the local minimum problem. A current domain D is divided into two parts: D1 and D2, where D1 has both a start configuration and target configuration, and D2 does not include both of them. Because the domain D1 has a path from the start to the target configuration in the free space, it is guaranteed that a robot can reach the target. Repeating that the domain D1 is undated as a new domain D, the domain D is reduced.

3. SPLINE SURFACE INTERPOLATING

ARBITRARY BOUNDARIES

ٻ

A surface generation method, which is one of the geometric modeling technologies, is used in the design field etc. as one that interpolates among given boundaries. While an ordinary method of surface generation involves interpolating four boundary edges, we have developed a method in which arbitrary boundaries can be interpolated [7]୊ The surface can interpolate an arbitrary shaped boundary such as a concave edge, a convex edge and a hole and the surface can be generated in real-time. These characteristics can be applied to motion planning for a mobile robot. We apply a distance-weighted function as a function of

artificial potential, which blends distances from each boundary with a reduction in computational time compared with other analytical methods. A spline surface is generated from a new domain created by removing unnecessary parts from a current domain.

㪯㪰㪱㫆㫌㫋㪼㫉㩷㪹㫆㫌㫅㪻㪸㫉㫐㫀㫅㫅㪼㫉㩷㪹㫆㫌㫅㪻㪸㫉㫐㪬㪭㪦㪦

Fig. 1 Spline surface generation from arbitrary boundaries Let p be a parameter in an N-dimensional parametric

space and the parametric space is one-to-one mapped to the free space FS. There, the free space FS should be parameterized to a parametric space “a domain D”. Define ȍi as each boundary element of the domain D. An (n+1)-dimensional surface S (p) at a parameter p is given by Eq. (1). , (1)

)

(

)

(

)

(

1

p

B

p

S

i N i i

¦

M

where (2)

»

¼

º

«

¬

ª

»

¼

º

«

¬

ª

)

(

)

(

)

(

)

(

)

(

)

(

p

b

p

B

p

x

p

S

i i i

_z

The parameter p of the Eq. (1) is a point p (u,v) in a two-dimensional parametric space. As shown in Fig. 1, a surface is formed by mapping the domain that has outer boundary and inner boundaries into a three-dimensional space using Eq. (5).

(3)

1 )

(

1

¦

N i i

p

M

))

,

(

))

,

(

)

,

(

1

v

u

b

v

u

d

v

u

N _i _i i i i

B

S

_¦

)

(5)

Here, Bi(p) and ĳi(p) are the boundary data ȍi for a

parameter p and a blending function for the boundary data respectively. An (n+1)-dimensional surface S(p) is a hyper surface that consists of a scalar potential ĭ(p) and a configuration x(p). Bi(p) comprises a boundary

configuration bi(p) and a potential zi(p) that is set to the

boundary.

»

¼

º

«

¬

ª

»

¼

º

«

¬

ª

)

(

,

))

,

(

))

,

(

)

,

(

)

(

)

,

(

)

,

(

)

,

(

v

u

b

z

v

u

b

y

v

u

b

x

v

u

v

u

y

v

u

x

v

u

i i i i i i i

B

p

S

(6)

The Eq. (1) provides a potential field by giving an appropriate potential to each boundary and by applying a distance from a boundary as well as Khatib’s method [2]. However, while Khatib’s method [2] obtains potential from a part of boundaries, the Eq. (1) gives potential in consideration of all the boundaries. In other words, the Eq. (1) provides potential in consideration of global space. This contributes to global motion planning for a robot in spite of no guarantee of local minimum reduction.

In other words, x and y of an ordinary surface means a configuration and z of that means a potential. The blending function ĳi(p) is a function of the distance parameters di,

and di is a function of u and v୊ Biis a function of the

boundary parameter biୈbi is a function of u and v୊

When a current parameter is p, then the configuration of a robot is given by x (p) and the potential by ĭ (p). By calculating Eq. (4), a robot sets the next parameter as

)}

(

{ p

p

)

'

K

grad

(4)

Next, we explain the distance and boundary parameters. For a given point P in a domain, the distance parameter di of an edge Ei shown in Figure 2 is given by

(3)

Fig. 2 Distance parameter of an edge in a domain 0 2 1

L

d

_i

ୈ

PA

L

1 ,

L

2

PB

,

L

0

AB

,

where di indicates distance from the edge Ei. The

trajectory for a constant di forms an ellipse.

The boundary parameter bi of an edge Ei is obtained by the next equation by using the distance parameters of bothٻ contiguous edges Ei-1 and Ei+1.

)

/(

₁ ₁ 1 i

i i i

d

b

The boundary parameter changes from 0 to 1 and is used in order to obtain the boundary data and a potential. Then, a blending function ĭi is given by the following equation.

¿

¾

½

¯

®

)

_¦

N i i i i

u

v

d

1

)

/

1 (

/

)

/

1 (

)

,

(

,where Bi is a positional vector of an edge. The blending function includes the next characteristics on each boundary.

䋩

䋨㪸㫋㩷

0 )

,

(

lim

,

1 )

,

(

lim

0 0 i

u

v

d i

u

v

i

j

di j

z

)

o o

ޓ

0 ) , ( w ) w j i b v u _ୈ

(

,

)

₀

w

)

w

j i

d

v

u

lim

(

,

)

(

)

0 i i di

u

v

b

B

S

o

4. DOMAIN REDUCTION PROCESS Simple application of a spline surface may cause the problem of a local stop. A spiral area in Fig. 3 shows an example causing such a problem. A robot cannot reach a goal G from a start point S and stops at a point L because there is a point with high potential near one with low potential like points H.

To resolve the problem, the unnecessary domain area is reduced in order to remove the effects of a near edge with high potential as follows:

(1) Search the nearest point of a boundary from a robot The nearest points NL and NR from a robot are searched

from a target point G along both sides of a boundary. Here NL is the nearest point that is found clockwise from the goal G and NR is the nearest point that is found counterclockwise from G (See Fig. 4).

E

i

L

0

B

ଢ଼

L

୍

L

2

_E

_i+1

P(u,v)

E

i-1

ଢ଼

Fig. 3 A local stop

Fig. 4 Search of the nearest points along a boundary

(a) Step 1 (b) Step 2

R

G N_R NL

Vertices that intersect with the domain boundary

A R AL D1R D1L intersections

ٻ

G N R NL A R AL

R

removed area

(c) Step 3 (d) Step 4

Fig. 5 Domain Reduction Process (2) Search of erasable point

This process checks whether a robot can see the vertices NL and NR by judging whether lines NL-R and NR-R

㪩

㪞 _㪥㪩㪥㪣㪝㫆㫌㫅㪻㩷㫍㪼㫉㫋㫀㪺㪼㫊㩷㩷㪘㪩㪘㪣㪡㫌㪻㪾㪼㩷㫎㪿㪼㫋㪿㪼㫉㩷㫃㫀㫅㪼㫊㩷㪺㫉㫆㫊㫊㪹㫆㫌㫅㪻㪸㫉㫐㩷㫆㫉㩷㫅㫆㫋 (counte clockwiser

search) (clockwise search)

㪩

㪞㪥㪩㪥㪣㪡㫌㪻㪾㪼㩷㫎㪿㪼㫋㪿㪼㫉㩷㫃㫀㫅㪼㫊㪺㫉㫆㫊㫊㩷㪹㫆㫌㫅㪻㪸㫉㫐㩷㫆㫉㩷㫅㫆㫋

㪩

㪞㪥㪩㪥㪣 (clockwise search) (counte clockwiser search)

(4)

intersect the boundary or not. If the lines intersect the boundary, the vertices NL and NR are necessary in order that the robot may arrive at a target point G (see Fig. 5).

5.2 Domain reduction for inner obstacles

In case of the existence of an inner obstacle shown in Fig. 10, the domain reduction process erases even a necessary vertex by judging whether a robot can see a vertex. Then, if the reduced domain does not contain the current configuration, a robot cannot reach the goal configuration. Because the purpose of the reduction process is to narrow a domain where a robot can move, the object to be reduced is the outer boundary of a domain. Therefore, in the case that a domain contains obstacles, the reduction process can be performed without any problems by neglecting inner obstacle.

Next, find vertices AL and AR next to the vertices of NL and NR (see Fig. 5(b)). These vertices can be seen by the robot. Then repeat the same process until finding a vertex that a robot cannot see. Fig. 5 (c) shows the found vertices DL and DR.

Because the robot cannot see the vertices DL and DR, they are not needed in order for the robot to arrive at the target point G. If the domain after the reduction has the goal and current configurations respectively, there is a path along which the robot arrives at the goal configuration. Thus, there is no problem caused by reduction in area. If the domain does not contain the current configuration, the domain reduction process is retried until the domain contains the current configuration. Fig. 5 (d) shows the situation after the domain reduction process. The elimination process contributes toward guiding a robot to a target point without a local stop. Because the original environment can be easily recovered by restoring the previous environment, a robot can be moved to a different goal along the way.

obstacle R

G

R

G

(a)

(b)

Fig. 7 Problem of domain reduction

5. OBSTACLES IN A GIVEN DOMAIN

5.1 Movement of obstacles in an area given

6. EXPERIMENT The previous chapter introduced a navigation method

using a spline surface and domain reduction. In addition, a robot should consider obstacles that exist in the given domain and disturb a mobile robot. Moreover, it is necessary for a mobile robot to avoid or wait for moving obstacles. Here, we represent a wall as an outer boundary and an obstacle as an inner boundary respectively. And applying the predetermined potential to each boundary, a mobile robot moves within the domain by reflecting the whole potential.

6.1 Experimental Method

This chapter describes some experiments to prove the effects of the proposed algorithm. We perform the following experiments to check whether the algorithm can operate properly. Experiments are performed for four environments with a different maze shown in Fig. 9.

It is necessary that robot navigation has a consideration of moving obstacles in the given domain. Therefore, we apply the predetermined potential to the obstacles so that the whole potential can change quickly with them. The change in potential is reflected in order that a mobile robot can move in the given domain deciding appropriate plans automatically such as “stop”, ”detour”, ”wait” and ”go”. Fig. 6 shows the change in potential when a obstacle moves from left to right.

(a)ٻ ٻ ٻ ٻ ٻ ٻ ٻ ٻ ٻ ٻ ٻ ٻ ٻ ٻ ٻ ٻ (b) Fig. 6 the change in potential with a moving obstacle

(a) Environment A (b) Environment B

(c) Environment C (d) Environment D Fig. 9 Environment with a different maze

(5)

[1] Simple application of a spline surface

Only a proposed spline surface is applied to each environment. The purpose of the experiment is to investigate the effect of the spline surface for the navigation of a mobile robot and then to find the problem.

[2] Application of a spline surface and domain reduction In the addition of experiment [1], the domain reduction process is applied to each environment. The purpose of the experiment is to examine the effect of the domain reduction. [3] Experiment for a moving obstacle

Moreover, in the addition of experiment [2], a moving obstacle is applied to each environment. The purpose of the environment is to check whether a robot can avoid or wait for the moving obstacle properly without any collision.

6.2 Experimental Results

[1] Simple application of a spline surface

Fig. 10 shows the experimental results in the case of a simple application of a spline surface. There, the arrows describe the route lines of a mobile robot from start to target configurations. The mobile robot avoided the obstacle and arrived at a target in the case of the environments A, B and C. However, it could not arrive at the target in the case of the environment D.

(c) Environment C (d) Environment D Fig. 10 Simple application of a spline surface [2] Application of a spline curve and domain reduction

Fig. 11 shows the experimental results. There, the arrows describe the route lines of a mobile robot while the cut walls show a half way result by the domain reduction.

A mobile robot succeeded in reaching the target configuration in all cases, so that it moved from the start to

the target configurations avoiding the obstacle.

(c) Environment C (d) Environment D Fig. 11 Application of a spline curve and domain

reduction

(c) Environment C (d) Environment D Fig. 12 Experiment for a moving obstacle [3] Experiment for a moving obstacle

Fig. 12 shows the experimental results. There, arrows describe the route lines of a mobile robot and dotted lines shows the route line of obstacles, while cut walls show the half way result by domain reduction.

(6)

In this experiment, a mobile robot could stop, avoid an obstacle and arrive at the target in the case of environments A and B. Moreover, a mobile robot could wait, avoid an obstacle and arrive at the target in the case of environments C and D.

The result of the experiment 1 shows that the characteristic of global navigation which involves a spline surface works effectively despite the simple application of a spline surface. Moreover, the addition of domain reduction could remove the problem of a local stop. A robot plans paths globally using an arbitrary boundary spline and relieves the problem of local minimum.

In addition, we have confirmed that a mobile robot can stop to wait for and avoid a moving obstacle by adapting appropriate actions such as “stop”, ”detour” and ”wait”; selected automatically depending on a given environment. In addition, the proposed method has shown that a mobile robot can arrive at a target configuration despite the existence of a moving obstacle.

7. Conclusion

This paper has proposed the application of an arbitrary boundary spline and an area elimination method to motion planning for a robot. The following results have been obtained.

(1) An arbitrary boundary spline provides global planning and an elimination method reduces the local minimum. Moreover, the proposed method can operate in real-time.

(2) By setting a moving obstacle to an inner boundary of an arbitrary boundary spline, a robot can move to a target position in real-time; avoiding obstacles.

Future work will involve application of the proposed method to a real robot that can move capturing an environment using certain sensors.

REFERENCES

[1] Jun Oota㧘Daisuke Kurabayashi㧘Tamio Arai㧦 Introduction to Intelligent Robots㧘Corona Publishing Co.㧘2001

[2] O.Khatib: Real-time Obstacle Avoidance for Manipulators and Mobile Robots, International Journal of Robotic Research, Vol.5, No.1, pp.90-98(1986) [3] Keisuke Sato㧦Global Motion Planning using a

Laplacian Potential Field㧘Journal of the Robotics Society of Japan㧘Vol.11, No.5, pp702-709(1993) [4] J.Barraguand, J-C. Latombe: Monte-Carlo Algorithm

for Path Planning with Many Degrees of Freedom, Proc.1990 IEEE Int. Conf. Robotics and Automation, pp.1712-1717(1990)

[5] E.Rimon, D.E. Koditschek: Exact Robot Navigation Using Artificial Potential Function, IEEE Trans. Robotics and Automation, Vol.8, No.5, pp.501-518(1992)ٻٻ

[6] Seiji Sugiyama㧘Sadao Akishita: Path Planning for Mobile Robot at a Crossroad by Using Hydrodynamic Potential㧘Journal of the Robotics Society of Japan㧘Vol.16, pp.839-844(1998)

[7] K.Kato: N-sided Surface Generation form Arbitrary Boundary Edges, Curve and Surface Design, Vanderbilt University Press,(2000)173-182㧚

Motion Planning for Mobile Robots Using a Spline Surface

1. INTRODUCTION