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

Download
# Improving the velocity of CPLO path planning technique