# creating small roadmaps for solving motion planning problems[精选推荐pdf]

Creating Small Roadmaps for Solving Motion Planning Problems∗Roland Geraerts and Mark H. Overmars Institute of Information and Computing Sciences Utrecht University, 3508 TB Utrecht, the Netherlands {roland,markov}@cs.uu.nlAbstract—In robot motion planning, many algorithms have been proposed that create a roadmap from which a path for a moving object can be extracted. These algorithms generally do not give guarantees on the quality of the roadmap, i.e. they do not promise that a path will always be found in the roadmap if one exists in the world. Furthermore, such roadmaps often become very large which can cause memory problems and high query times.We present a new efficient algorithm that creates small roadmaps for two- and three-dimensional problems. The algo- rithm ensures that a path is always found (if one exists) at agiven resolution. These claims are verified on a broad range of environments. The results also give insight in the structure of covering roadmaps. Keywords—motion planning, small roadmaps, PRMI. INTRODUCTIONA central problem in robotics is planning a collision-free path for a moving object in a rigid environment. In the lasttwo decades, efficient algorithms have been devised to tacklethis problem. They are successfully applied in fields such as mobile robots, manipulation planning, CAD systems, virtual environments, protein folding and human robot planning. See e.g. the books of Latombe [1] and Lavalle [2] for many interesting results. In these application areas, it is often desirable that a pathbetween a start and goal configuration (which is a placement of the moving object) is quickly found. For example, mainte- nance studies in industrial installations [3] can be performedmore efficiently if an engineer does not have to wait long fora solution. In other fields, e.g. in games, only a fixed small amount of calculation time is available to compute the path. If this calculation takes too long, the game may halt. Single shot methods, such as RRT [4], aim at quicklyconnecting a start configuration to a goal configuration. Although good performance is achieved (compared to the traditional methods described in [1]), they may still be too slow as the calculations are performed on-line. In contrast, the Probabilistic Roadmap Method (PRM) enables the con- struction of a path in real-time [5]–[8]. The PRM consists of two phases: a construction phase (off-line) and a query phase (on-line). In the construction phase, a roadmap (graph)∗This research was supported by the Dutch Organization for Scientific Research (N.W.O.). This research was also supported by the IST Programme of the EU as a Shared-cost RTD (FET Open) Project under Contract No IST-2001-39250 (MOVIE - Motion Planning in Virtual Environments).is built, representing the motions that can be made in the environment. Nodes in the roadmap correspond to randomlychosen collision-free configurations. When a node is added, asimple local planner is employed to connect the configuration to some useful neighbors in the roadmap. A neighbor isuseful if its distance to the new configuration is less thana predetermined constant. Configurations and connections are added to the roadmap until the roadmap is dense enough.In the query phase, the start and goal configurations are connected to the roadmap. Then, the path can be obtained by a Dijkstra’s shortest path query. A drawback of the PRM is that a resulting roadmap often contains many redundant nodes and edges, in particular when the environment contains one or more narrow passages. Over the years, many improvements have been suggested to tackle the narrow passage problem [9]–[11] but those solutions often lead to large roadmaps. Such large roadmaps increase the time needed to extract a path and can require a vast amount of memory which may not always be available. Furthermore, the roadmap may contain many short edges which complicates the smoothing phase that often follows a query phase [8]. Another drawback is that a path may not always be found in practice while one exists. This occurs for example when the roadmap is not dense enough. A variant of the PRM that aims at keeping the roadmap small is the visibility based roadmap [12]. This techniqueonly connects configurations to useful nodes. Usefulness is determined as follows: when a new node cannot be connected to other nodes it forms a new connected component and is labeled useful. If it connects two or more components it is also labeled useful. If it can be connected to just one component it is not labeled useful. Although this approach prunes the roadmap a lot, it is often slower than other variants of the PRM as the approach is too strict in rejecting nodes [6].We propose a new efficient method that creates a small roadmap for two- and three-dimensional problems. Our method will ensure that a valid query can always be connected to the roadmap and that a path is always found (if one exists) at a given resolution. Because the roadmap is small, smoothing can easily be applied in the preprocessing phase, leading to instant query answers. We will elaborate on the properties of the approach in section II. In section III we show the outline of the method and we work out its details in section IV. In section V we show some experiments on differentscenes and in section VI we conclude that our algorithm successfully creates small roadmaps for a large diversity of environments.II. REACHABILITYAn important question is how to determine when the roadmap is dense enough, i.e. when should the algorithm ter- minate? Many motion planning techniques such as the PRM and RRT are probabilistically complete [5], i.e. whenever a path exists, the probability that it will be found convergesto one as the computation time goes to infinity. As there is no guaranteed upper bound, the running time is not a practical termination criterion. Many authors terminate themethod when a path between a specified start and goal is found. However, this does not guarantee that this roadmap can solve every query. In [13], we used the reachability criterion to determine when a problem has been solved, i.e. a problem has beensolved if a roadmap G = (V,E) covers the free configuration space (Cfree) and captures its connectivity. We define coverage and maximal connectivity as follows:Definition 1 (coverage). G covers Cfreewhen each configu- ration c ∈ Cfreecan be connected using the local planner to at least one vertex v ∈ V .Definition 2 (maximal connectivity). G is maximally con- nected when for all vertices v′,v′′∈ V , if there exists a path in Cfreebetween v′and v′′, then there exists a path in G between v′and v′′.Coverage ensures that every query (which consists of astart and goal configuration) can be directly connected to the roadmap, as is required to solve the problem. If there exists a path (in Cfree) between the start and goal configuration, then maximal connectivity ensures that a path between them can be found in the roadmap. We will use this criterion as a termination criterion in the remainder of this paper. Figure 1 shows an environment whose free space is covered by two (white) vertices and is connected via one extra (black) vertex. The reachability region for the upper left vertexhas been drawn. Each configuration in this region can be connected with a straight line to the vertex, so a three-nodegraph suffices to solve this problem. In section IV we will explain how such a reachability region can be computed.III. REACHABILITYROADMAPIn this section we show how to create a small roadmap thatsatisfies both the coverage and maximal connectivity criteria. The idea is to compute a small number of guards that ’see’ the complete free space (coverage). These guards are thenconnected via connectors to fulfill the maximal connectivity criterion. The resulting roadmap is then pruned to obtain an even smaller roadmap. Computing the minimum number of guards corresponds to the well known art gallery problem which is NP-hard [14]. AsFig. 1.The coverage and maximal connectivity criteria have been met: the reachability regions of the white vertices cover the free space and are connected via the black vertex.we want to create a roadmap for a possibly large environment with many obstacles, exact algorithms are infeasible. There- fore, we will use a heuristic to create and place these guards (which are added as nodes to the roadmap). Globally speaking, the method works as follows. To get the free space covered as fast as possible, we place the guards on locations where they may see a large part of the space. Locations on the medial axis are good candidates as they have a large clearance from the obstacles and thus have an increased probability of having a large reachability region. To prune the number of candidate guards, a new guard is only accepted if it cannot be seen by guards that have already been placed. It can occur that all points on the medial axis are seen by the guards while the free space has not been fully covered yet. In such a case we choose a point in a location which initially cannot be seen by other guards. Then we retract this point to the medial axis to increase the expected size of its reachability region. (Note that this guard will be seen by other guards.) An advantage of placing all guards on the medial axis is that ’good’ roadmaps are produced [11]. We keep adding new guards until the free space has been completely covered. We connect the guards by placing connectors in the over- lapping reachability regions of the guards. We consider all pairs of guards whose regions overlap. For each pair, we add the connections and connector to the roadmap. Finally, we prune this roadmap by transforming it to a Steiner Tree. Such a tree is a shortest network that does not throw away guards (but is allowed to remove connectors) and keeps the connected components connected. Then we add all remaining connections and create a minimal spanning tree to reduce the length.Theorem 1 (Coverage of Cfree). The above methods lead to a complete coverage of Cfree.Proof: The medial axis is a connected structure if the free space in which a robot operates is also connected [15]. Hence, the medial axis is a complete representation for motion planning purposes. We start with selecting points on the medial axis and add them as nodes to the roadmap. If all points on the medial axis are covered by the guards but there are still points in Cfreethat have not been covered yet, we select such a point which we retract to the medial axis. Asthis retraction can be performed in a straight line [11], the original point will be covered by the retracted point. Because we keep adding new guards until the free space is completely covered, the coverage criterion will be met. This criterionwill remain satisfied when the roadmap is pruned as these heuristics never remove guards.Theorem 2 (Maximal connectivity of Cfree). The abovemethod satisfies the maximal connectivity criterion.Proof: Consider a path Π from node v′to node v′′that lies in Cfree. As Cfreeis completely covered, there exists foreach configuration π ∈ Π a node vi∈ V that sees π. Now consider the sequence of different nodes vi∈ V that sees theconfigurations on Π. (If multiple nodes in V see a particularconfiguration π, we consider the node vihaving the smallestindex i.) If adjacent configurations πjand πj+1are seen by node vi, virepresents the path between these configurations. If they are seen by different nodes viand vi+1, there exists a path between these two nodes (possibly via a connector) inthe graph as these configurations lie in the overlappingregions of viand vi+1. (A degenerate case is when the regions of vi and vi+1touch and do not overlap. This case can be handled by placing an extra connector on the boundary of these two regions.) Because a path between v′and v′′(in the graph) can be mapped to a path in Cfree, this roadmap will obey the maximal connectivity criterion. The maximal connectivitycriterion will remain satisfied when the roadmap is pruned as the heuristics only remove edges that are part of cycles.IV. ALGORITHMICDETAILS The main operation in our technique is the computation of the reachability regions. An exact computation of these regions would involve intricate and practically infeasiblecalculations in the configuration space C. To make the calcula- tions feasible, we approximate the C-space by discretizing it. As a consequence, this approach is limited to low-dimensional C-spaces. We performed experiments with both two- and three dimensional C-spaces. We discretize a d-dimensional C-space as follows. First, we create a d-dimensional grid. For each cell in this grid wecheck whether the corresponding configuration collides with the obstacles and update the cells appropriately, i.e. we put the value 0 in the cell if it collides and 1 otherwise. We will use this grid in the remainder of the algorithm, see Figure 2(a). In section IV-A, we show for a given resolution how to get the free space covered and in section IV-B we show how to get this space maximally connected. Finally, we show in section IV-C how the roadmap can be pruned.A. Coverage We need a set of cells that reside on the medial axis. Thisset can be efficiently computed by the medial axis transform(a) C-space(b) MAT(c) DT(d) Overlay(e) GuardsFig. 2.The creation of candidate guards. Figure (a) shows the free (white) cells of the discretized C-space of Figure 1. Figure (b) shows the cells of medial axis transform and (c) the distance transform. Dark cells correspond to a large distance to the closest obstacle while light cells correspond to a small distance. In (d), the overlay of the MAT and DT is shown. Finally, (e) shows the four guards having the largest distance in the overlay.(MAT) which is a well known technique in mathematical morphology. We use the algorithm presented in [16]. This algorithm is a two-pass dynamic program that computes the MAT in O(n) time where n is the number of cells in the grid. See Figure 2(b) for an example. As guards having a larger distance to the obstacles should be handled earlier than guards having a small distance, we need to compute their distances to the obstacles. These can beefficiently computed by the distance transform (DT) in O(n) time, see Figure 2(c). Like the MAT, the DT is also computed by a two-pass dynamic program, see e.g. [16]. We determine the clearance for each medial axis cell by overlaying the MAT with the DT, see Figure 2(d). These cells are then sorted by decreasing distance using bucket sort in linear time. We store these cells, which are candidates for guards, in a list M, see Figure 2(e). We keep adding guards from this list to the roadmap until the free space has been fully covered (or when all points of M have been handled). As we have already mentioned,we first only add guards that cannot be seen by guards that have already been added. If the space is not covered when all medial axis points have been handled, we consid