ARTIGO TÉCNICO F. Gómez-Bravo, A. Ollero*, F. Cuesta*, D. López Escuela Politécnica Superior, Universidad de Huelva, Spain {fernando.gomez, diego.lopez}@diesia.uhu.es *Escuela Superior de Ingenieros Universidad de Sevilla, Spain {aollero, fede}@cartuja.us.es *Corresponding author: fernando.gomez@diesia.uhu.es
A NEW APPROACH FOR CAR-LIKE ROBOTS MANOEUVRING BASED ON RRT ABSTRACT This paper presents a new approach for the extension of the Rapidly Exploring Random Trees (RRT) path-planning algorithm to car-like vehicles, providing simple solutions in complex scenarios with low computational cost. The proposed method combines the advantages of RRT for exploring the free space with a technique for the generation of feasible paths developed from the concept of restricted manoeuvres.
I. INTRODUCTION
II. RAPIDLY EXPLORING RANDOM TREES (RRT)
Mobile robots motion planning involves the problem of searching for collision-free paths connecting a starting and a goal configuration. The path must accomplish several constraints imposed by obstacles and the robot kinematics. This topics has been largely approached in the literature [2], [8], [7], [19]. Especially the randomized methods have focused considerable attention in recent years [15], [16], [17]. For instance, in the randomized potential field approaches, random walks are used to help escape if the search becomes locked on a local minimum [2]. Another example of a randomized planning technique is the probabilistic roadmap method [16], [17]. This technique built up a graph in the configuration space by choosing many configurations at random, and using a local planner to connect pairs of nearby configurations. This approach might require the connections of thousand of configurations to find a solution. Furthermore, in general, the connection problem can be as difficult as designing a non linear controller.
The RRT is a path planning algorithm which provides continuous paths connecting a initial configuration, qinit, with a goal configuration, qgoal by applying a random method. Each configuration specifies the position and orientation of the robot in a 2D or 3D scenario. Obstacles and constraints can be defined. Let C be the set of configurations that the robot might have, regardless of existing obstacles. Thus, Cfree denotes the set of collisionfree configurations. It is assumed that a metric R is defined in C.
The Rapidly Exploring Random Trees [1], or RRT arises to improve the solutions to the path-planning problems. In this method there are not potential function because is a purely randomized technique. Also it does not require as many configurations as the probabilistic roadmap and is easy to extend to high-dimensional configuration spaces, yet to include different constraints. Many versions have been published, like the RRT Connect [4] or the ERRT [6], to fit RRT to different scenarios. There are several approaches for extending the RRT algorithms to nonholonomic vehicles [3], [6]. This article proposes applying the RRT algorithm to car-like robots similarly as was applied to differential drive vehicles in [18]. The method can be easily extended to more complicated nonholonomic system and provides simple solutions. This new approach presents a better performance and allows the RRT to work without dealing with kinematic constraints, improving the algorithm efficiency. The paper is organized as follows: At the following section the RRT method is described. The traditional application of the RRT algorithm in nonholonomic systems is introduced in section 3. Section 4 presents the basis for car-like vehicles manoeuvring. Section 5 is devoted to explain the proposed approach for applying the RRT algorithm to car-like vehicles. Finally, in section 6, simulation results are presented. The paper ends with the conclusions and the references.
[ ]
robótica
The basic RRT, [1], is shown in Fig.1. The algorithm defines a data structure, which starts at the qinit configuration, and determines where the new configurations are attempted to be added. These appears as the vertices of a tree that grows exploring the space. The aim is to bias the exploration towards unexplored collision-free areas. In order to achieve this objective the algorithm chooses a random configuration of Cfree, called qrand. Then the Extendd function selects the tree´s nearest vertex, qnear, by using the R metric. From qnear, a motion toward qrand, with a fixed distance H is simulated, see Fig.2. If a collision is detected, the algorithm rules out the growth toward qrand, else a new vertex qnew is added to the tree.
BUILD_RRTT (qinit) Tree[0]= qinit For k = 1 to Kmax qrandd = Randomized_conff(); Extend(Tree, qrand); Next k Returns Tree Figure 1 . Basic RRT algorithm
There are several implementations of the RRT algorithm. The first have only one tree rooted at the initial configuration [1]. The tree grows until a vertex falls at a distance H to the goal. Then, a path is returned. In order to improve the performance, new versions were developed. These new approaches increase the density of the probability function close to the goal, then, the growth of the tree is biased toward it [5]. New improvements arose with the Bidirectional planners [4]. These