Vol. 44 No.2
SCIENCE IN CHINA (Series E)
April 2001
Robot path planning in globally unknown environments based on rolling windows ZHANG Chungang (~R ~ ~1) & XI Yugeng
(J$ ~ JJt)
Institute of Automation, Shanghai Jiaotong University, Shanghai 200030, China Correspondence should be addressed to Zhang Chungang ( email:
[email protected]) Received May 5, 2000
Abstract In this paper, robot path planning in globally unknown environments is studied. Using the rolling optimization concept in predictive control for reference, a new strategy of path planning for a mobile robot, based on rolling windows, is proposed. The method makes full use of the real-time local environmental information detected by the robot and the on-line path planning is carried on in a rolling style. Optimization and feedback are combined in a reasonable way. The convergence of the planning algorithm is also discussed. Keywords: robot path planning, rolling planning, convergence, predictive control.
The mobile robot path-planning problem means finding a proper moving path for the robot from a designated start point to a designated goal point in a workspace with obstacles. The path should be collision-free so that the robot can bypass obstacles safely. In known environments, the planning problem can be solved by off-line global planning. Furthermore, some of the indexes of the motion can be optimized. This has been extensively studied and has generated many literatures' 1-5]. Configuration space, generalized cones, artificial potentials, generalized Voronoi graphs, visibility graphs, etc. have been used for path planning. But in general, the environmental information for path planning is not complete or even unknown. The robot can only detect local sensory information of the environment. People have proposed a few methods and strategies for path planning in unknown environments. But most of these methods have high requirements on robots and can hardly guarantee the global convergence[6-9J . Borenstein[7] used virtual force field method to solve the collision-free problem in unknown environments. The method cannot guarantee the robot reaching the goal successfully in some situations and may result in instability[S]. Lumelsky[9J studied nonheuristical methods of path planning in unknown environments. In their methods, the robot must remember some special points in the workspace, and the planning is always guided by a global convergence criterion. However, the paths are not ideal in many cases because of lack of optimization. Sankaranarayanan'P'' made some improvements by making the robot strore more enviromental information. Iyengar[lO] solved this problem by imparting the learning capability to the robot. The robot explores the obstacle terrain using sensors and incrementally builds the terrain model. The global optimality of the paths is gradually achieved as the learning proceeds. But the computation burden of this method is heavy and there is much redundant information. In fact, the path-planning problem of mobile robot in globally unknown environments concerns how to make full use of detected local information to plan a path that is not only feasible but
132
SCIENCE IN CHINA (Series E)
Vol. 44
also optimal. Both optimization and feedback should be considered in the planning. Predictive control [11], which has been widely used in process control, is one of the successful models of the combination of the two mechanisms and shows us a good way to solve the robot path-planning problem. In this paper, we use the concept of rolling optimization in predictive control for reference and apply it to robot path planning in globally unknown environment. An effective pathplanning method based on rolling windows is proposed. The feasibility and convergence of the planning algorithm are also discussed.
1
Problem formulation and preliminary knowledge
Consider a mobile robot (Rob) in a two-dimensional unknown workspace (WS) with finite size. The robot is required to move autonomously from a start point (PinJ to a goal point (p goal) successfully in finite time. We add the following restrictions on Rob and WS. Restrictions on Rob. Rob has no priori knowledge of the workspace and has no memory of the detected environmental information. At any instant, Rob can only scan a local circular area around itself, whose radius is equal to r , Rob can move omnidirectionally in the workspace with a step length do < € :::;: r) . Restrictions on WS. WS is defined as a convex polygon that is arbitrarily cluttered with finite number of static obstacles (Obsl, Obs2, "', Obs n). Rob is modeled as a point by "enlarging" the obstacle-size to account for actual robot dimension and the requirement on safety. The boundaries of enlarged obstacles are safe regions along which the point robot can move. Obs i ( i = 1 ,2, ... , n ) is convex and its boundary is a smooth curve. The radius of the curvature of each point on the boundary is not longer than 0 (0 is a constant and 0 < r ) and the center of the curvature is inside the obstacle. Obstacles do not interact with each other or with the workspace boundary . Obviously, the above path-planning problem cannot be solved by global planning algorithms for lack of priori environmental information . We first give some related definitions for robot path planning. Assume that all the points in WS make up a closed convex set Wand its boundary is denoted by aW. All the points in Obs i ( i = l , 2, ... , n ) make up a closed convex set 0 i and its boundary is denoted by
(J 0i'
Then we have O, eWe R 2 and
o, { o,
n OJ
=
-:;6 j,
(1)
where i , j = 1 , ... , n . Set up the system Cartesian coordination 2: 0 in WS. Thus, V PEW has definite coordinate (x, y). At instant t , the position of Rob in WS is denoted by P R ( t) and its coordinate is (XR ( t), YR ( t ) ). Let t =0 be the start instant of the planning. In the following discussion, we use superscript" 0" and" c" to represent the interior and the complement of the corresponding set, respectively.
Definition 1. P is called a feasible point for PEW and P ~ 0 i ( i = 1 , ... , n ): The set of all feasible points in W is called a feasible domain and denoted by FD. P is called a forbidden point for P ~ W or P E 0 i ( i = 1 , '" , n ), The set of all forbidden points in W is called forbidden domain and denoted by NFD. Obviously,
No.2
ROBOT PATII PLANNING IN GLOBALLY UNKNOWN ENVIRONMENTS
133
n
FD = W
n (n ( On e) ,
( 2)
i =I
n
NFD =
we U ( U On
(3)
.
i = I
Definition 2. V P o , Pf E FD , T = [ 0 , 1 ] , if a conti nuous mapping FS: T- FD makes FS ( 0 ) = Po and FS ( 1) = Pf , then FS is called a feasible path from P o to Pf in W. FS (0) and FS (l ) are called the start point and the end point respectively . The image set FS ( T ) is called a feasibl e passage from Po to Pf in WS and denoted by FP ( p oPf ) . Obviously, FP (POPf ) makes up a continuous curve con nec ting p o( x o , Yo) with Pf ( xf ' Yf) in WS and a feasibl e path means a mapp ing that generates the feasible passage . One feasi ble passage may be generated by different feasible paths . Definition 3. V P o, Pf E FD, the se t of all feasibl e path s from P o to P, in FD is called a fixed end feasible path set, denoted by T FD ( Po Pf) . Definition 4. d ( P i' Pj ) denotes the distance from P i to Pj ' which is defin ed as
d ( P i , Pj Definition 5.
)
= J (Xi
- x)2 + (Yi - y)2 .
Given a feas ible path FS *
there always exists d ( FS *
( t 2) , P )
f
E T' FD (
P oPf ), if
V t l'
(4) t 2E
[0 , 1], t I < t2'
< d ( FS * ( t I ) , Pf ), then FS * is calle d a strictly nearer
feasible path from P o to Pf ' Intuitively , with the above rest rictions on the works pace. if P o , PfE FD , then there must exist a strictly nearer feasible path from P o to Pf . In the following , we give the relative theorems but omit the proofs . Theorem 1. V P o, Pf E FD, there must exist a feasib le path FS from P o to Pf; that is , r m (poPf ) ¥-
Theorem 2. ( po Pr ) ·
There must exist a stric tly nearer feasi ble path FS * from P o to Pf in T FD
In the following , a robot path -p lanning algorithm is propos ed . One ca n eas ily prove that it guarantees the robot moving along a strictly nearer pat h. The algorithm consists of the following steps: Algorithm 1. Strictly nearer feasible path planning . Step 1. Move directly to the goal until one of the following occ urs : ( 1) The goal is reached . The planni ng stops. ( 2) The boundary of an obstacl e is encountered . Go to Step 2. Step 2. Move along the proper side of the obsta cle' s bou ndary that can decrease the distance from the current position to the goal, until one of the following occ urs : ( 1) The goal is reached . The planning stops. (2) The conce rned obstacle does not appear in the li ne lin king the curre nt posi tion with the goal . Go to Step 1 .
2 Path planning based on rolling window s The essence of the path- plan ning problem is to plan an optimal moving path for robot in the workspace. If all environmental informati on is known , one ca n plan an optimal path for robot by some effective algorithms. But if the robot has no information about the environmen t , it ca n only use on-line feedback information to plan its path step by step . In this case, it is impossible to achieve global optimality. The steps of Algorithm 1 show that the robot only uses point- neighbor-
134
SCIENCE IN CHINA (Series E)
Vol. 44
hood information to decide its moving direction at each instant and the detectable environmental information on its local neighboring area is not fully used. So it is just a "look-and-move" planning method without optimization of the path. Although it is unable to carry out global optimization with incomplete information in uncertain environment, optimization can also be taken into account to some extent based on the available feedback information. The key problem is how to make full use of the known information. Ref. [12] generalized the basic principles of predictive control used in industrial process control to solve the problem of planning, scheduling and decision in uncertain environments. Three principles were proposed that make full use of known information for prediction and estimation, carry on local optimization by rolling windows and update the old knowledge with feedback information. These principles exhibit the combination of optimization and feedback. They can be effectively applied to the path-planning problem described in this paper, as the robot has no priori global knowledge but on-line detected local information. The path-planning algorithm based on rolling windows depends on real-time local environmental information detected by the robot and the on-line path planning is carried on in a rolling style. At each step of rolling, Rob generates an optimal subgoal based on the local detected information by a heuristical method and plans a local path in the current rolling window. Then it carries out the current strategy (moving a step along the local path). With the rolling window moving forward, Rob obtains newer environmental information. Thus, optimization and feedback are combined in the rolling process. Definition 6. Win ( PR( t » = 1 PIP E W, d ( P , PR( t ) ) ~ r i is called the vision scope of Rob at P R( t), namely the rolling window of Rob at P R( t), where P R(t) E FD. With the above definition, we give the rolling planning algorithm as follows: Algorithm 2. Path planning based on rolling windows. Step O. Initialize the start point (p inJ, the goal point (p goal) , workspace (WS) and vision scope (r), step length (e:) . Step 1. If the goal is reached, the planning stops. Step 2. Update the environmental information in the current rolling window. Step 3. Generate a local optimal subgoal P sub ( t ) . Step 4. Plan a proper local path in the current rolling window by Algorithm 1 according to the subgoal and known local environmental information. Step 5 . Move a step along the local path. The step length is e ( 0 < e: ~ r ) . Step 6. Return to Step 1 . In the above algorithm, Step 3 generates subgoals in the following way: At instant t, the rolling window is known as Win ( PR( t ) ). If P goal E Win ( PR( t ) ), Rob selects P goal as its subgoal , i. e. P sub ( t ) = P goal' Otherwise, Rob uses heuristical function f ( p) = g ( p) + h ( p) to choose a point on the boundary of the rolling window as the subgoal P sub ( t), which minimizes f( p), namely minf(P) = g(P) + h(P) (5) p
s.t. P
E aWin(PR(t».
g ( p) denotes the cost from current position P R ( t ) to P, which can be estimated by the position of P and the known environmental information in the current window. h ( p) denotes the cost from P to the goal. Since the environmental information out of the window is unknown, h ( p) is usually estimated by the distance from P to the goal. This method of choosing subgoal reflects the compromise of the requirement for global optimization and the restriction of finite local informa-
No.2
ROBOT PATH PLANNING IN GLOBALLY UNKNOWN ENVIRONMENTS
135
tion. It is a natural choice of trying to pursue global optimization in the given environment. In this paper, we lower the requirement for optimization to reduce the planning burden by just setting the value of g ( p) according to the position of P (in feasible domain or not); that IS,
=
{O, if (p E FD), + 00, if (p E NFD). Thus, the problem of choosing subgoal can be transformed into the following optimization problem: min] = mind(P, (6)
(p)
g
p
s.t. P
r;».
E aWin(PR(t»
n FD.
In the following, we give the proofs of the existence of subgoals and the local strictly nearer feasible path in Algorithm 2. Lemma 1. aWin( PRe t ) FD ¥- (P. Proof. If aWin ( P R ( t » intersects more than one obstacles, then it must pass through the boundaries of the obstacles, say, a 0;, i E 11,2, ... , n I. Since a Qi c FD, it is easily known that aWin(PR(t»n FD¥-(P. IfaWin(PR(t» only intersects one obstacle, say, 0;,
n
and aWin(PR(t»n FD = (P, then aWin(PR(t» C ot. Thus we have Win(PR(t» C ot. It is contradictive to P R(t) E FD. So it must be true that aWin( P R(t» FD ¥- (P. By Lemma 1, we know that P sub ( t ) will always exist. If there exist more than one subgoals, Rob can choose one arbitrarily. Theorem 3. There must exist a feasible path LFS in Win ( PR( t ) ), which makes LFS (O)=PR(t), LFS(l)EaWin(PR(t» , LFS(dWin(PR(t»rE(O,l), and V"I' "2E [0, 1J, "I < "2' d ( LFS ( "2)' P sub ( t ) ) < d ( LFS ( "I ), P sub ( t ) ). LFS is said to be a strictly nearer local feasible path from PR( t ) to P sub ( t ) in Win ( PR( t ) ) . Since PR ( t), P sub ( t) E FD and by Theorems 1 and 2, the above theorem can be easily proved.
n
3 Convergence analysis of the rolling planning algorithm Definition 7. If there exists t«> 0, such that PR( tf) E j PIP E W, d ( P, P goal) < € I , then it is said that Rob reaches goal at instant tf. . Next, we prove that Rob will always reach P goal safely from the start point P ini in finite time by using Algorithm 2 if the workspace satisfies the given restrictions. In the following, PR( t + i:lt) and P sub ( t + i:lt) denote the new position and the new subgoal of Rob respectively after Rob moves a constant step length, where i:lt > and it is a variable if Rob's moving speed changes. Lemma 2. Using Algorithm 2, if P goal ~ Win ( PR( t ) ), then P sub ( t ) is strictly nearer to P goal' That is, d ( P sub ( t2), P goal) < d ( P sub ( t 1), P goal) for V t l ' t2 > 0, t 1 < t2' where t 1 , t2 are any two start instants of the local planning.
°
Proof. According to Steps 4, 5 in Algorithm 2, it is known that Rob moves along a strictly nearer local feasible path LFS in its rolling windows. That is, d ( P sub ( t ), PR(t + i:lt» < d ( P sub ( t), PR( t ) ) . Since d ( P sub ( t + i:lt), PR( t + i:lt) ) = d ( P sub ( t), PR( t ) ) = T, it holds true that P sub ( t ) E Wine PR(t + i:lt». With P sub (t), P goal E FD, there must exist a strictly nearer feasible path
SCIENCE IN CHINA ( Series E)
136
Vo!' 44
FS ' from P sub ( t ) to P goal in WS, whose corresponding passage is denoted by FP ' ( P sub ( t ) P goal) ' Noting that P goal f!. Win e PRe t ) ) , SO FP ' ( Psub ( t ) Pgoal) 3W in( P R( t + .1t) ) =;6 (P.
n
n
Let e : E FP' ( P sub ( t ) P goal) 3Win( PR( t + .1t ) ) , then d ( e : , P goal) < d ( P sub ( t) , P goal) ' According to the subgoal choosing method, P sub ( t + .1t) must satisfy
d ( P sub ( t + .1t), P goal) ~ d ( P " , P goal) • Since t is arbitraril y chosen, the lemma is easily proved. Lemma 3. If there exists i ; such that P goal E Win ( PR( t w ) ) , then P goal E Win ( PR( t ) ) for V t > t w ' Proof. According to the rolling plannin g algorithm , if P goal E Win ( PR( t w ) ), then P sub ( t w ) = P goal - If II P R ( t w ) - P goal II ~ e , the plann ing stops . Otherwise , Rob moves along a strictly nearer local feasible path (LFS ) to P sub ( t ) during further rolling periods, which are generated by Step 4. Therefore, it is true that d(PR(t) , P goal) < d(PR( t w ) , P goal ) < r for V t > t w ' That is , P goal E Win ( PR ( t ) ) can be guarant eed from then on . Lemma 4. There must exist a finite t w such that P goal E Win ( P R ( t w ) ) • Proof . We prove the lemma by contradiction . Assume that the lemma is false , that is, P goal f!. Win ( PR( t ) ) for V t . By Lemma 2, it is known that d ( P sub ( t ), P goal) is monotonouslydecreasing and bounded if P goalf!.Win (PR ( t ) ) . Therefore , d (P sub(t ) , P goa1 ) must converge to a limit . Without losing generalit y , assume lim d ( P sub ( t ) , P goal ) = d, ~ O. (* ) , ......+
OIl
A) X sub ( t ) + Axgoal ' Y = ( 1 - A) Ysub ( t ) + AY goal ' 0 ~ A ~1 1, H= l P l d ( P , P goal ) ~ d" PEw f, P,(t)= 3HnL(t). By( *), we can conclude that lim d ( P sub ( t), P, ( t ) ) = O. It is easily known that there must exist tF such that P, ( t ) E Let L ( t )
= 1P ( x , y) I x = ( 1 -
t-+oo
FD for V t > t p ; Let z( t ) = r - d ( P Rt i + .1t) , P sub ( t)) . By Algorithm 1 and the restri ctions on the workspace, it can be easil y proved that z ( t) has no limit with time going on . Noting that lim d (P sub( t) , P, ( t ) ) = 0 , there must exist t , ~tFsuch that d (P sub(t J , P, ( tJ )< z ".
t-
+ OI:
( t,) . Then we have d( PR( t, + .1t) , P, ( tJ ) ~ d (PR (t , + .1t), P sub( t, ) ) + d (P sub( tJ, P, ( tJ ) < r ; that is, p, ( t J E Wine PRe t, + .1t) ) " . If d, =0 , then P goal E Win e P R( t, + .1t)). It contradicts the assumption . If d, > 0, it is easily proved that d ( P sub ( t, + .1t ), P goal ) < d, . Also it contradicts the assumption that d ( P sub ( t ) , P goal) is monotonously decreasing and converges to d, . So there must exist a finite t w such that P goal E Win e P R (t w ) ) ' Theorem 4. There must exist a finite t .; such that P goal E Win( P R ( t ; )) for V t > t w • It can be easily proved by Lemmas 3 and 4 . Theorem 4 indicat es that after finite times of rolling planning P goal will finally be inside the Rob' s rolling window and keep staying inside the windows fro~ then on. Lemma 5. If P goal E Win( PR( i ; ) ), then there must exist a finite tf ( tf ~ t w ) such that Rob reaches P goal at tf . Proof. If P goal E Win ( PR( t w ) ) , then P sub ( t ) = P goal for V t ~ t; according to Algorithm 2. If II P R ( t w ) - P goal II ~ €, Rob reaches the goal and tf = t w ' Otherwise, before reaching the goal, Rob moves strictly nearer to P sub ( t) in each step of the rolling process by executing Step 4 and Step 5 of Algorithm 2. Therefore , d ( P R ( t ), P sub ( t )) is monotonously detf ~ w ) creasing with time going on and its lower bounda ry is zero . So there must exist a finite
t/
t
137
ROBOT PATH PLANNING IN GLOBALLY UNKNOWN ENVIRONMENTS
No.2
such that d ( PR (tl)' P goal) < € Namely, Rob reaches P goal at tlo Theorem 5. V Pint' P goal E FD, Algorithm 2 guarantees that Rob from Pin! in finite time. Proof. By Theorem 4, we known that there exists a finite t w such (t w » for V t > t w Also by Lemma 5, we know that there exists a finite d ( PR ( tf)' P goal) < e Moreover, every new position generated by Step 0
0
0
can reach P goal safely that P goal E Win ( P R t/ t/~ t w ) such that 5 during each rolling
period is always. on the feasible path planned by Step 4, that is, P R ( t ) E FD for V t E [ to , tfJ. So Rob can reach P goal safely from P ini in finite time In fact, for any convex polygonal obstacle, if all its edges are smooth curves, the curvature is a constant and radius of each point except the vertices on the edges is not longer than () () < r ) and the center of curvature is inside the obstacle, then all the above conclusions hold true. 0
«()
4 Simulation results Fig. 1 shows the simulation process of mobile robot path planning in globally unknown environment, which is planned by Algorithm 2. In unknown environment, Rob uses real-time local detected information inside its vision scope and performs rolling planning. The unknown obstacles are marked with gray color and the detected ones with black color in the figure The simulation shows that Rob can move from the start point (S) to the goal point ( G) successfully by the rolling planning algorithm. Since at each time the path planning is carried on in a smaller window and only a feasible path is planned, Algorithm 2 can not only solve the path-planning problems in unknown environment, but also has high speed and high efficiency. 0
Fig. I.
Robot path planning based on rolling windows.
Fig. 2 shows two paths planned by Algorithms 1 and 2 respectively in the same workspace.
138
SCIENCE IN CHINA ( Series E)
Vol. 44
Algorithm I only uses point-neighborhood information and the goal position to decid e its moving direction at each instant. However , Algorithm 2 considers the optimal point to the goal on the boundary of its rolling window by choosing the subgoal and makes Rob go towards the subgoal. The desire of global optimization is reflected in each period of rolling planning. So the path plann ed by Algorithm 2 is smoother than that plann ed by Algorithm 1 . It should be pointed out that since we have reduced the optimization requirem ent in the current algorithm, it can only improve the optimality through a more smooth and direct path in static environments. However, in the environment with unknown dynamic obstacles, using local detected environmental information to find a more optimal and obstacle avoidance path will be more advantageous. We will discuss it in another pape r .
Fig . 2 . Comparison of the paths planned by Algorithm I and Algorithm 2 . ( a) The path planned by Algorithm I ( 202 steps); ( b) The path planned by Algorithm 2 ( 174 steps ) .
5
Conclusions
Mobile robot path-planning problm in unknown environments is one of the key issues in robotics . Lacking priori global environmental information, the robot cannot execute the off-line global planning. On the other hand , in real applications the robots are often restricted by their effective sensory scopes and have no global vision sights. So the planning can only depend on realtime detected local information. In this paper, using the rolling optimization concept in predicti ve control for reference, a new path-planning method based on rolling windows for globally unknown environments is proposed . Although the robot has no priori knowledge and no memory of detected information , it can still reach the goal success fully by using real-tim e detected local information. Not only is the computation burden highly reduced , but also the global convergence is guaranteed by effective combination of the mechanisms of optimization and feedback in rolling planning. These advantages make the rolling planning algorithm well suitable to the changes in the environment and is particularly suitable to robot path planning in dynamic uncertain environment . Ackn owledgements This work was supported by the National 973 Plan (Grant No. GI99803 04 15) and the National Natural Science Foundation of China ( Grant No. 69774004 ) and the National 863 Program ( Grant No. 9805-18 ) .
No.2
ROBOT PATH PLANNING IN GLOBALLY UNKNOWN ENVIRONMENTS
139
References I. 2. 3. 4. 5. 6. 7. 8. 9. 10.
11. 12.
Schwartz, J . T . , Sharir, M. , On the " Piano Movers" problem : I. The case of a two-dimensional rigid polygonal body moving amidst polygonal barriers, Comm. Pure App!. Math., 1983, 36 : 345-398 . Lozano- Perez, T ., Spatial planning : a configuration space approach, IEEE Trans . on Computers , 1983 , 32 ( 2 ): 108- 120 . Crowley, J. L., Navigation for an intelligent mobile robot, IEEE Trans . on Robotics and Automation, 1985 , 1( 1) : 31-4 1 . Brooks, R . A., Solving the find-pa th problem by good representation of free space , IEEE Trans. on Systems, Man and Cybernetics', 1983, 13(3 ) : 190-197 . Takahashi, O . , Schilling, R . J. , Motion planning in a plane using generalized Voronoi diagrams, IEEE Trans . on Robotics and Automation, 1989 , 5( 2 ) : 142-1 50 . Sankaranarayanan , A. , Vidyasagar, M. , A new path planning algorithm for moving a point object amidst unknown obstacles in a plane , in Proc. IEEE Conf. on Robotics and Automation , Nice , France, 1990, 1930-1936. Borenstein , J . , Koren, Y., Real time obstacle avoidance for fast mobile robots, IEEE Trans. on Systems , Man and Cybernetics, 1989, 19 ( 5 ) : 1179-11 87. Tilove , R . B., Local obstacle avoidance for mobile robots based on the method of artificial potentials, in Proc. IEEE Conf. on Robotics and Automation, Nice, France, 1990, 566- 57 1 . Lumelsky, V . J . , Algorithm and complexity issues of robot motion in an uncertain environment , Journal of Complexity, 1987, 3: 146-1 82. Iyengar, S . S., Jorgensen , C . C ., Rao, S . V . N. et al. , Learned navigation paths for a robot in unexplored terrain , in Proc. 2nd Conf. on Artificial Intelligence Applications and Engineering of Knowledge Based Systems, Miami Beach, Florida , 1985, 11-13 . Xi Yugeng, Predictive Control ( in Chinese ), Beijing : National Defense Industry Press , 1993 . Xi Yugeng, Predictive control of generalized control problem in dynamic uncertain environment, Control Theory and Applications ( in Chinese), 2000, (I ) : 5 .