Improving the velocity of CPLO path planning technique
Marcelo O. Silva∗
Roseli A. F. Romero
Willian C. Silva†
Departamento de Ciências da Computação, ICMC, USP,
13560-970, São Carlos, SP - Caixa Postal 668
E-mail: [email protected], [email protected], [email protected]
Abstract
Our purpose is to develop algorithms for controlling multiple autonomous mobile robots, in
dynamic environments. One of the main tasks that a robot should accomplish in such environments is to move itself to another region of the environment without colliding with obstacles
(static or not). In general, this task is done by using a path planning algorithm.
When inserted into a dynamic environment, it is crucial that the robot makes decisions
(reactive or deliberative) in a short time. Therefore, path planning cant spend much run-time,
because it can reduce the efficiency of the robot operation, since it has to perform other tasks
simultaneously (e.g., mapping of the environment and localization).
Locally Oriented Potential Fields (CPLO) proposed by [3], Equation 1, is a path planning
technique that is applicable to multiple robots. This is based on numerical solutions of Boundary
Value Problems which generate a given trajectory of a particular Elliptic Partial Differential
Equation. This method is able to find a path (if they exists) from actual robot position to the
goal and it can control multiple autonomous mobile robots, each one with distinct behaviors.
∇2 P (x, y) + (x, y) h∇P (x, y), v(x, y)i = 0
(1)
where P : Ω → R and, Ω = {(x, y) ∈ R2 | xo ≤ x ≤ xf , yo ≤ y ≤ yf }
As it was proposed in [1], CPLO method has a step of numerical solution of a linear system.
Using Finite Difference Method, we obtain the computational molecule showed in Equation 2.
 1
if the cell (i, j) is

4 [(1 + λvx )pi+1,j + (1 − λvx )pi−1,j +



(1 + λvy )pi,j+1 + (1 − λvy )pi,j−1 ]
inside the influence
area of robot k
(2)
pi,j =




1
otherwise
4 (pi+1,j + pi−1,j + pi,j+1 + pi,j−1 )
where ∆x = ∆y = δ is the step size from the mesh, λ = δ
2 and P (xo +j ×∆x, yo +i×∆y) ≈ pi,j .
Using computational molecule of Equation 2 at all points of the mesh, we obtain a linear
system that can be solved by the iterative Gauss-Seidel method, which consists of building
successive approximations (from a “initial guess”) of the solution through some error measure.
In this work, was used as error measure the Euclidean distance (squared) between two successive
approximations.
Although it has been proven (satisfying some conditions) that the Gauss-Seidel method
is convergent to CPLO, it was found that initial guess can affect the speed of convergence.
We tested, initially, four strategies: Uniform distribution on [0, 1] (Strategy 4), Geometric Mean
Potential (Strategy 3), Average Potential of Previous Relaxation (Strategy 2) and Keep Previous
Solution (Strategy 1).
Using the control system proposed in [2] and a modified version of the robot soccer simulator
R
presented in [4], we evaluated 1100 times each strategy (see Figure 1(a) - 1(b)), with a Intel
R
Core2Quad Q6600 2.4GHz and 4Gb RAM DDR2.
∗
†
bolsista de mestrado Fapesp
bolsista institucional de IC da USP
1106
(a) Time (microseconds)
(b) Number of iterations
Figure 1: Comparison of the Strategies
Strategies
1
2
3
4
µtime
5299.84
362485.03
473124.55
461609.13
σtime
11433.26
38176.31
83133.81
81725.77
95% CItime
[4624.17, 5975.50]
[360228.95, 364741.11]
[468211.66, 478037.44]
[456779.45, 466438.82]
µiterations
12.83
813.00
1258.95
1258.82
σiterations
29.48
0.00
22.33
22.43
95% CIiterations
[11.08, 14.57]
[813.00, 813.00]
[1257.63, 1260.27]
[1257.49, 1260.14]
Table 1: Statistics. Time is on µs
As it can be seen in Figures 1(a) - 1(b) and in Table 1, the strategy 1 has a great advantage
over the others, i.e., it converges faster and in few iterations. Then, it will be incorporated to
the system developed in [2].
Keywords: Path Planning, Path Planning BVP based, Numerical Methods, Robotics
References
[1] M. O. Silva, R. A. F. Romero and G. A. P. Caurin (2008). Analysis of locally oriented
potential fields. In Proceedings of IROBOT 2008 - 3rd International Workshop on Intelligent
Robotics ( L. P. Reis, L. Correia, N. Lau, R. Bianchi eds.), Lisbon University Institute ISCTE, Lisbon, Portugal, October 14th 2008 . ISBN 972886208-3.
[2] M. O. Silva and D. O. Melo and B. H. Gonçalves and R. C. R. Silva and R. A. F. Romero
(2008). O Sistema Integrado do Time de Futebol de Robôs USPDroids. Team Description
Paper on Latin American Robots Competition
[3] G. Faria (2006). Uma Arquitetura de controle inteligente para múltiplos robôs. PhD thesis,
ICMC-USP São Carlos.
[4] D. O. Melo and R. A. F. Romero (2009). O simulador 3d para futebol de robôs USPDS.
Technical Report 339. ICMC-USP São Carlos
1107