Topological Nearest-Neighbor Filtering for Sampling-Based Planners (日本語訳)

Topological Nearest-Neighbor Filtering for Sampling-Based Planners

ICRA2018 Read Sandstrom, Andrew Bregger, Ben Smith, Shawna Thomas, and Nancy M. Amato https://parasol.tamu.edu/publications/download.php?file_id=1008

Abstract

Nearest-neighbor finding is a major bottleneck for sampling-based motion planning algorithms. The cost of finding nearest neighbors grows with the size of the roadmap, leading to significant slowdowns for problems which require many configurations to find a solution. Prior work has investigated relieving this pressure with quicker computational techniques, such as kd-trees or locality-sensitive hashing.

  • 最近傍探索は、サンプリングベースのモーションプランニングアルゴリズムの主要なボトルネックです。最寄りの近隣諸国を探すコストはロードマップのサイズが大きくなるにつれて大きくなり、解決策を見つけるために多くの構成を必要とする問題の大幅な減速につながります。以前の研究は、kd木または局所性に敏感なハッシングのようなより速い計算技術でこの圧力を軽減することを調査した。

In this work, we investigate an alternative direction for expediting this process based on workspace connectivity. We present an algorithm called Topological Nearest-Neighbor Fil- tering, which employs a workspace decomposition to select a topologically relevant set of candidate neighbor configurations as a pre-processing step for a nearest-neighbor algorithm. We investigate the application of this filter to several varieties of RRT and demonstrate that the filter improves both nearest- neighbor time and overall planning performance.

  • この作業では、ワークスペースの接続性に基づいてこのプロセスを促進するための代替の方向性を調査します。トポロジー的最近傍フィルタリングと呼ばれるアルゴリズムを提示します。これは、最近傍アルゴリズムの前処理ステップとして、トポロジ的に関連性のある候補隣接構造のセットを選択するためにワークスペース分解を使用します。このフィルタのいくつかの種類のRRTへの適用を調査し、このフィルタが最近傍時間と全体的な計画パフォーマンスの両方を改善することを実証します。

I. Introduction

Sampling-based motion planners such as PRM [1] and RRT [2] explore a problem by sampling random configura- tions for a robot and connecting them to nearby neighbors. In this context, the nearness of two configurations is determined by a distance metric defined over the entire configuration space. An important component in the process of connecting configurations is a nearest-neighbor search, which determines which existing configuration qold will be tried when connect- ing to a new sample qnew.

  • PRM [1]やRRT [2]のようなサンプリングベースのモーションプランナーは、ロボットのランダム構成をサンプリングし、それらを近隣の近隣に接続することによって問題を探ります。これに関連して、2つの構成の近さは、構成空間全体にわたって定義された距離メトリックによって決定される。構成を接続するプロセスの重要な要素は、最近傍検索です。これは、新しいサンプルqnewに接続するときにどの既存の構成qoldを試すかを決定します。

Nearest-neighbor finding is a major bottleneck for sampling-based planners. A brute-force scan requires linear time for each connection attempt, while more advanced methods such as those based on kd-trees [3] approach log- arithmic time with a sufficiently large number of configura- tions. However, prior work has focused primarily on utilizing faster computational techniques as opposed to leveraging the shape of the free space.

  • 最近傍検索は、サンプリングベースのプランナにとって大きなボトルネックです。ブルートフォーススキャンでは、接続の試行ごとに線形時間が必要ですが、kd-trees [3]などのより高度な方法では、十分な数の構成で対数時間に近づきます。しかしながら、従来の研究は、自由空間の形状を利用することとは対照的に、より速い計算技術を利用することに主に焦点を合わせていた。

In this work, we investigate how workspace connectivity can be employed to identify a reduced set of candidate neighbors for consideration by a nearest-neighbor algorithm. The algorithm, called Topological Nearest-Neighbor Filter- ing, aims to select a reduced set of candidate neighbors which are topologically relevant to the query configuration. This is realized by leveraging a cell decomposition of the free workspace to define topologically similar neighborhoods of workspace. Roadmap configurations are mapped to these neighborhoods to support quickly locating the configurations

  • 本研究では、最近傍アルゴリズムによる検討のために、候補隣接集合の縮小集合を識別するためにワークスペース接続性をどのように採用できるかを調査する。トポロジカル最近傍フィルタリングと呼ばれるアルゴリズムは、クエリ構成に位相的に関連性のある候補近傍のセットを減らすことを目的としています。これは、無料のワークスペースのセル分解を利用して、トポロジ的に類似したワークスペースの近傍を定義することによって実現されます。ロードマップ構成はこれらの近隣にマッピングされ、構成を素早く見つけることをサポートします。

in a given neighborhood. When presented with a nearest- neighbor query q, the filter locates the set of decomposition cells that are topologically relevant to q and selects only the set of configurations within as candidates for the subsequent nearest-neighbor search.

  • 与えられた近所で。最近傍クエリqが提示されると、フィルタは、qに位相的に関連する分解セルの集合を見つけ、その中の構成の集合のみをその後の最近傍探索の候補として選択する。

In this work, we present the filter algorithm and experi- mental validation demonstrating its usefulness in several en- vironments with four RRT-type planners (RRT [2], SST [4], Dynamic Region-biased RRT [5], and SyCLoP [6]). We show that the filter can improve both nearest-neighbor time and overall planning performance, and also that it can be adapted to bias roadmap connection along any desired flow through a workspace decomposition graph.

  • 本研究では、4つのRRT型プランナー(RRT [2]、SST [4]、Dynamic Region-biased RRT [5]、およびSyCLoP)を用いたいくつかの環境におけるその有用性を示すフィルターアルゴリズムと実験的検証を示す。 [6])。我々は、フィルタが最近傍時間と全体的な計画性能の両方を向上させることができ、そしてまたそれがワークスペース分解グラフを通して任意の所望の流れに沿ってロードマップ接続を偏らせるように適応できることを示す。

II. Related Work

Nearest-neighbor finding has attracted significant attention in sampling-based motion planning research as a primary performance bottleneck. Two primary avenues have been investigated, which are exact and approximate methods. Approximate methods attempt to return a nearby neighbor as opposed to the precise nearest neighbor.

  • 最近傍発見は、サンプリングベースの運動計画研究において、主要な性能ボトルネックとして大きな注目を集めている。正確で近似的な方法である2つの主要な道が調査されました。近似メソッドは、正確な最近傍とは対照的に、近くの隣接を返すことを試みます。

A popular method for exact nearest-neighbor finding in a motion planning context employs a kd-tree to quickly compute the nearest neighbor [7]. A later work re-iterates on this method to develop a partitioning strategy which better respects the nuances of the orientation components [8]. The use of kd-trees is also observed for nearest-neighbor prob- lems in machine learning. Other structures such as metric and cover trees have also been suggested, although empirical evidence suggests that these are not significantly faster than kd-trees in problems of moderate size and dimension [9].

  • 運動計画の文脈における厳密な最近傍探索のための一般的な方法は、最近傍を迅速に計算するためにkd木を使用する[7]。後の研究ではこの方法を繰り返して方向成分のニュアンスをより尊重する分割戦略を開発した[8]。 kd木の使用は、機械学習における最近傍問題にも見られます。メートル法やカバーツリーなどの他の構造も提案されていますが、経験的な証拠によると、これらは適度なサイズと次元の問題でkdツリーよりも大幅に高速ではないことを示しています[9]。

However, other researchers have noted that kd-trees per- form little better than brute-force when the problem di- mension is moderate to large [10]. Such difficulties have spurred investigation in approximate nearest-neighbor meth- ods, which aim to trade a relatively small sacrifice in accuracy for a larger gain in computational speed. Locality- sensitive hashing is a well-known class of approximate methods which attempts to bucket similar samples together with some form of hashing scheme, and has been applied in both machine learning [11], [12] and motion planning [10]. An alternative approximate method from the motion planning realm is distance-based projection onto Euclidean space (DPES), which uses a projection from configuration space to a lower-dimensional Euclidean space before computing the neighbors [13].

  • しかし、他の研究者は、問題の大きさが中程度から大規模である場合、kd木はブルートフォースよりも少し優れていると指摘しています[10]。そのような困難さは近似的に最近傍の方法での研究に拍車をかけており、それは計算速度におけるより大きな利得と精度における比較的小さい犠牲を交換することを目的としている。ローカリティセンシティブハッシングは、類似のサンプルを何らかの形式のハッシングスキームと共にバケット化することを試みるよく知られたクラスの近似方法であり、機械学習[11]、[12]および運動計画[10]の両方に適用されている。運動計画の分野からの別の近似方法はユークリッド空間への距離ベースの投影(DPES)であり、これは近傍を計算する前に構成空間からより低次元のユークリッド空間への投影を使用する[13]。

The present work relies on a workspace decomposition, which is a partitioning of the free workspace into a set of discrete cells. Decompositions are a well-studied area

  • 現在の作業は、ワークスペースの分解に依存しています。これは、空きワークスペースを一連の個別セルに分割することです。分解はよく研究されている分野です

Fig. 1. An example scenario where proximity is not a good metric for the nearest neighbor. The start S and goal G are shown in green and red, and the roadmap is shown in blue. The planner is searching for a nearest- neighbor for the sample Q. The best neighbor is N , but nearest-neighbor algorithms which are not aware of free space will choose one of the two nodes on the other side of the wall (illustrated with dashed yellow lines).

  • 図1.近接が最近傍に適した測定基準ではないシナリオの例。スタートSとゴールGは緑と赤で表示され、ロードマップは青で表示されます。プランナはサンプルQの最近傍を検索しています。最良の隣接はNですが、空き領域を認識しない最近傍アルゴリズムは、壁の反対側にある2つのノードのうちの1つを選択します(破線で示します)。黄色い線)。

of computational geometry and are covered in standard texts [14]. In this context, we are primarily interested in graph-representations of a workspace decomposition as a means of discovering topological relationships between spe- cific cells which are relevant to the motion planning process. A prior method which makes use of a workspace decom- position for nonholonomic tree extension is the SyCLoP framework [6]. In this method, the tree is extended by selecting a roadmap configuration q from the front of a “discrete lead” extracted from a workspace decomposition graph using a search from start to goal. A random control is then applied from q to propogate the tree forward. This causes the tree to expand preferentially from the outermost samples along the discrete lead; this is effective in practice but cannot be applied to methods which bias the growth direction with sampling.

  • 計算幾何学のものであり、標準的なテキストでカバーされています[14]。これに関連して、運動計画プロセスに関連する特定のセル間の位相関係を発見する手段として、ワークスペース分解のグラフ表現に主に関心があります。非ホロノミックツリーの拡張にワークスペースの分解を利用する従来の方法は、SyCLoPフレームワークです[6]。この方法では、最初から最後までの探索を用いてワークスペース分解グラフから抽出された「離散リード」の前からロードマップ構成qを選択することによってツリーが拡張される。次に、ランダム制御がqから適用されてツリーが前方に伝播されます。これにより、ツリーは最も外側のサンプルから個別の誘導に沿って優先的に拡張されます。これは実際には効果的ですが、サンプリングで成長方向を偏らせる方法には適用できません。

In this work, we investigate a nearest-neighbor filter based on workspace connectivity that attempts to select the most pertinent configurations for the subsequent nearest-neighbor check. We note that workspace connectivity is an important factor in estimating the probability that a connection will suc- ceed because the local planning algorithms used in sampling- based motion planning are deliberately designed for small steps through configuration space, which implies a small or negligable displacement of the robot body in workspace. Our filter does not require the notion of a query, and can be adapted to respect any desired flow through workspace.

  • この研究では、後続の最近傍チェックのために最も適切な構成を選択しようとするワークスペースの接続性に基づいて最近傍フィルタを調査します。サンプリングベースのモーションプランニングで使用されるローカルプランニングアルゴリズムは意図的に配置空間の小さなステップ用に設計されているため、ワークスペースの接続性は接続が成功する確率を推定する重要な要素です。ワークスペース内のロボット本体私たちのフィルタは、クエリの概念を必要とせず、ワークスペースを通してあらゆる望ましいフローを尊重するように適応させることができます。

III. Method

We present Topological Nearest-Neighbor Filtering, which

  • トポロジカル最近傍フィルタリングを紹介します。

is based on three observations:

  • 3つの観測に基づいています。

1) For a given configuration q, other configurations which are not nearby in connected workspace are unlikely to be successfully connected to q, regardless of their Cspace proximity. For example, two configu- rations on the opposite side of a thin wall are very close in Cspace but quite far apart through connected workspace (Fig. 1).

  • 1)所与の構成qに対して、接続されたワークスペース内で近くにない他の構成は、それらのC空間の近接度にかかわらず、qにうまく接続される可能性が低い。たとえば、薄い壁の反対側にある2つの構成は、Cspaceでは非常に近接していますが、接続された作業領域ではかなり離れています(図1)。

2) As the roadmap grows in size, the set of configurations that are likely to be connected to q typically shrinks to a very small fraction of the roadmap.

  • 2)ロードマップのサイズが大きくなるにつれて、qに関連する可能性が高い設定のセットは通常ロードマップのごく一部に縮小されます。

3) The primary influence on the cost of a nearest-neighbor

  • 3)最近傍のコストに対する主な影響

check is the size of the candidate set.

  • checkは候補セットのサイズです。

The filter aims to identify a relatively small set of candidate neighbors for q which are likely to be successfully connected to q by examining the workspace topology. We refer to such configurations as “good candidates” for connecting to q.

  • フィルタは、ワークスペーストポロジを調べることによって、qへの接続に成功する可能性が高い、qに対する比較的少数の候補近傍集合を識別することを目的とする。我々は、そのような構成をqに接続するための「良い候補」と呼ぶ。

A convex cell decomposition of the workspace can be leveraged to locate such candidates by maintaining a map- ping between decomposition cells and roadmap configura- tions. Whenever configurations are added to the roadmap, they are also added to this mapping, referred to here as the “decomposition map”.

  • ワークスペースの凸セル分解は、分解セルとロードマップ構成との間のマッピングを維持することによってそのような候補を見つけるために利用することができる。構成がロードマップに追加されるときはいつでも、それらはこのマッピングにも追加され、ここでは「分解マップ」と呼ばれる。

The overall approach is to use the decomposition map to locate a neighborhood of cells C that contain good candidate neighbors for q. First, we locate the cell c that contains q. Then, a limited single-source shortest paths search (Alg. 3) outward from c through the decomposition graph identifies the neighborhood C that is near to c via a path through con- nected workspace. We say that cells meeting this criteria are “topologically relevant” when connecting to configurations in c. Once the neighborhood has been identified, the de- composition map provides the set of roadmap configurations that reside within. These configurations are passed to the nearest-neighbor algorithm as candidate nearest-neighbors. The filter’s role in planning is thus to minimize the work that the nearest-neighbor algorithm must perform.

  • 全体的なアプローチは、分解マップを使用して、qに対する良好な候補近傍を含むセルCの近傍を見つけることです。まず、qを含むセルcを見つけます。次に、分解グラフを介してcから外側への限定された単一情報源最短経路探索(図3)は、接続された作業空間を通る経路を介してcに近い近傍Cを識別する。この基準を満たすセルは、cの構成に接続するときに「位相的に関連性がある」と言います。近隣が識別されると、分解マップはその中に存在するロードマップ構成のセットを提供します。これらの構成は、最近傍候補として最近傍アルゴリズムに渡される。したがって、計画におけるフィルタの役割は、最近傍アルゴリズムが実行しなければならない作業を最小限に抑えることです。
A. Finding the Decomposition Cells

To find the decomposition cell

  • 分解セルを見つける

that holds a particular configuration q, we use the spatial degrees of freedom as a reference point p and say that q is “contained” by the cell c which contains p (as in [6]). The cell c can be located in time polylogarithmic in the number of decomposition cells [14], although in practice a simpler implementation is often adequate.

  • これは特定の構成qを保持するので、我々は基準点pとして空間自由度を使用し、qはpを含むセルcによって「含まれる」と言う([6]のように)。セルcは、分解セルの数[14]の中で時間多対数的に配置することができますが、実際にはより単純な実装で十分な場合が多いです。

A two-stage search can provide effective results: first, impose a uniform grid over the workspace and locate the voxel g containing q in constant time. Then, check each decomposition cell which contacts g and return the one that contains q (Alg. 1). Both the grid and the mapping from voxel to touched cells are computed once as a pre-processing step, so the second stage takes time linear in the maximum number of decomposition cells that touch a given voxel, which is usually very small for a well-formed decomposition.

  • 2段階検索は効果的な結果を提供することができる:最初に、ワークスペース上に一様なグリッドを課し、そして一定時間内にqを含むボクセルgを見つける。次に、gに接触する各分解セルを調べ、qを含むものを返します(Alg。1)。ボクセルからタッチされたセルへのグリッドとマッピングの両方が前処理ステップとして一度計算されるので、第2段階は与えられたボクセルに触れる分解セルの最大数で線形に時間がかかります。分解を形成した。

Algorithm 1 Find the decomposition cell associated with a designated point. The set of cells touching each grid voxel is computed once as a pre-processing step.

  • アルゴリズム1指定された点に関連する分解セルを見つけます。各グリッドボクセルに接触するセルの集合は前処理ステップとして一度計算される。
B. Mapping Decomposition Cells to Roadmap Vertices

While constructing the roadmap, a decomposition map is also created to map roadmap vertices to their containing

  • ロードマップの構築中に、ロードマップの頂点をそれらの包含マップにマッピングするための分解マップも作成されます。

cells and vice versa. Whenever a new vertex q is added to the roadmap, the process described above determines the containing cell c. The decomposition map is updated to make this information readily available for neighbor filtering (Alg. 2). After locating the workspace cell, the cell map update can be implemented in amortized constant time using a hash map from cells to vectors of configurations.

  • セルとその逆。新しい頂点qがロードマップに追加されるときはいつでも、上記のプロセスは包含セルcを決定する。分解マップは、この情報を近隣フィルタリングのために容易に利用可能にするように更新される(図2)。ワークスペースセルの位置を特定した後、セルマップ更新は、セルから構成ベクトルへのハッシュマップを使用して、償却された一定時間で実施することができる。

Algorithm 2 Updating and querying the cell map. We imply global structures for the maps to minimize parameters in this presentation, but this is not a requirement.

  • アルゴリズム2セルマップの更新と問い合わせこのプレゼンテーションでは、パラメータを最小にするためにマップのグローバル構造を意味しますが、これは必須ではありません。

Note that for planning methods which delete configura- tions from the roadmap, the deleted configurations must also be removed from the decomposition map. This can also be supported in amortized constant time with a hash map imple- mentation for the map from configuration to decomposition cell.

  • ロードマップから構成を削除する計画方法では、削除された構成も分解マップから削除する必要があります。これは、構成から分解セルまでのマップのハッシュマップ実装を使用して、一定の償却時間でサポートすることもできます。
C. Finding Candidate Neighbor Vertices

The decomposition cell c containing a sample configura- tion q identifies the immediate region of workspace contain- ing q. Assuming we could determine some neighborhood of cells C that are topologically relevant to c, the cell mapping can be employed to find a set of candidate neighbors for q in the neighborhood C.

  • サンプル構成qを含む分解セルcは、qを含むワークスペースの直近領域を識別する。 cに位相的に関連するセルCのある近傍を決定することができると仮定すると、近傍C内のqに対する1組の候補近傍を見つけるためにセルマッピングを使用することができる。

We now require a means to determine the neighborhood of other decomposition cells C that are topologically relevant to c. This set will be referred to as the candidate cells for c.

  • 我々は今、cと位相的に関連する他の分解セルCの近傍を決定する手段を必要とする。この集合はcの候補セルと呼ばれる。
D. Finding Candidate Cells

For any cell c, we can find the set of topologically relevant candidate cells C by conducting a single-source shortest paths search on the decomposition graph outward from c and stopping when some threshold distance δthreshold is exceeded (Alg. 3).

  • 任意のセルcについて、cから外向きに分解グラフ上で単一ソース最短経路探索を行い、ある閾値距離δthresholdを超えたときに停止することによって、位相的に関連のある候補セルCの集合を見つけることができる(図3)。

The discovered cells are topologically relevant to c be- cause the search follows the connected free space, and they are nearby because we enforce a maximum expansion distance δthreshold.

  • 探索は接続された空きスペースをたどるため、発見されたセルは位相的に関連性があり、最大拡張距離δthresholdを適用するためそれらは近くにあります。

Algorithm 3 Single-source shortest paths (SSSP) interface. Run an SSSP algorithm using a reduced set m of the decomposition graph’s adjacency map, and terminate when t is true. Return a map from each discovered cell to its score (distance from source) and successors.

Fig. 2. (a) Example where the straight-line distance between cell centers C1, C2 is not a good metric for the connected workspace distance. A better metric is to measure the path through the shared facet midpoint M . (b,c) An example of the candidate cells (shaded pink) shown with and without query relevance. The start S is shown in green and the goal G in red. The workspace decomposition is shown in beige, and the current roadmap is shown in blue. For illustration purposes, we use hops as the distance metric and set δthreshold = 1. (b) The query point Q is one hop from the nearest populated cell, so the candidate cells are the set of cells within two hops of Q. (c) The candidate cells are reduced when observing query relevance by ignoring edges that lead closer to the goal.

  • 図2.(a)セル中心C1、C2間の直線距離が、接続されたワークスペースの距離に対する適切な測定基準ではない場合の例。より良い測定基準は、共有ファセットの中点Mを通る経路を測定することです。 (b、c)クエリの関連性の有無にかかわらず表示された候補セル(ピンクの網掛け)の例。スタートSは緑色で、ゴールGは赤色で表示されます。ワークスペース分解はベージュで表示され、現在のロードマップは青で表示されます。説明のために、距離メトリックとしてホップを使用し、δthreshold= 1を設定します。(b)クエリーポイントQは最も近いセルから1ホップなので、候補セルはQの2ホップ以内のセルのセットです。 )クエリの関連性を観察するときに、目標に近づくエッジを無視することによって候補セルが削減されます。

Given two adjacent cells a and b,

  • 2つの隣接するセルaとbを考えます。

the line between their segments may cross into obstacle space, depending on the type of decomposition used and the shape of the workspace (Fig. 2.a). As such, the free space distance be- tween their centers is not necessarily equal to the Euclidean distance between cell centers. A simple approximation for the free-space distance is to measure the Euclidean distance along the line segments from the centers of a, b to the midpoint of the shared facet between them. Using this edge weighting avoids measuring virtual short-cuts through obstacle space which are not physically realizable.

  • それらのセグメント間の線は、使用されている分解のタイプとワークスペースの形状によっては、障害物のスペースに入ることがあります(図2.a)。このように、それらの中心間の自由空間距離はセル中心間のユークリッド距離に必ずしも等しいとは限らない。自由空間距離の簡単な近似は、線分に沿ってa、bの中心からそれらの間の共有ファセットの中点までのユークリッド距離を測定することです。このエッジ重み付けを使用することは、物理的に実現可能ではない障害物空間を通して仮想ショートカットを測定することを回避する。
E. The Sampling Frontier

While the above method locates good candidate cells for some query cell c, there are no roadmap configurations within this neighborhood. In this case, we must look further outward to find a relaxed neighborhood that does contain configurations.

  • 上記の方法はいくつかの質問セルcに対して良好な候補セルを見つけるが、この近傍内にはロードマップ構成はない。この場合、構成を含むリラックスした近隣を見つけるために、さらに外側を見なければなりません。

is entirely possible that

  • それは完全に可能です

The nearest such neighborhood is the “sampling frontier” F of grid cells that are populated and reachable from c by traversing only unpopulated cells. This represents the subset of the roadmap that is topologically nearest to c because any other configurations would have to connect through one of these regions to reach c. This neighborhood is different from the overall roadmap frontier in that c may be embedded within obstacles or within a gap in free space coverage. It follows that F will be at most the entire roadmap frontier and may be significantly smaller.

  • そのような最も近い近傍は、未移入セルのみをトラバースすることによって移入され、cから到達可能なグリッドセルの「サンプリングフロンティア」Fである。これは、cに位相的に近いロードマップのサブセットを表します。これは、cに到達するには他の構成がこれらの領域の1つを介して接続する必要があるためです。この近傍は、cが障害物の中や空き領域の範囲の隙間の中に埋め込まれている可能性があるという点で、全体的なロードマップのフロンティアとは異なります。その結果、Fはせいぜい全体のロードマップのフロンティアとなり、大幅に小さくなる可能性があります。

The neighborhood F may be very large and far from the original cell c if c is far from the covered free space, and would seem to be not topologically relevant to c in that case. However, there is no set of candidate cells with better topological relevance, and the set of configurations in F will typically be much smaller than the entire roadmap.

  • cがカバーされた自由空間から遠く離れている場合、近傍Fは非常に大きく、元のセルcから遠く離れている可能性があり、その場合、位相的にcに関連しないように思われる。しかしながら、より良好な位相的関連性を有する一連の候補セルは存在せず、そしてFにおける一連の構成は典型的にはロードマップ全体よりはるかに小さいであろう。

It is also possible that there are populated cells far from c which are connected by an unpopulated path, and also populated cells much closer to c (i.e., as in Fig. 2.b). In this case, work would be wasted in discovering the entire frontier after the most useful portion has already been identified.

  • また、cから遠く離れた人口の多い経路によって接続されている人口の多いセル、およびcにずっと近い人口のあるセル(すなわち、図2bのように)が存在することも可能である。この場合、最も有用な部分がすでに識別された後に、全フロンティアを発見することに労力が費やされることになる。

Algorithm 4 Find a sampling frontier.

roadmap grows in size.

  • ロードマップは大きくなります。

To avoid this problem, we can select a limited frontier instead by terminating the search early. After visiting the first populated cell at distance D from the source, the search will be terminated upon visiting a cell at least D + δthreshold from the source. This selects only the most promising cells as the limited sampling frontier (Alg. 4).

  • この問題を回避するために、検索を早く終了することによって、代わりに限定されたフロンティアを選択することができます。ソースから距離Dのところにある最初のセルを訪問した後、検索はソースから少なくともD +δしきい値のセルを訪問した時点で終了する。これは、限られたサンプリングフロンティアとして最も有望な細胞のみを選択する(図4)。

This frontier may be empty if there are no roadmap config- urations in any cell that is connected to c - in this case, there are no connectable configurations in the roadmap. A non- empty frontier is guaranteed to hold at least one configuration by construction, which will be relatively nearby through connected workspace compared to other configurations in the roadmap.

  • cに接続されているセルにロードマップ設定がない場合、このフロンティアは空になります。この場合、ロードマップに接続可能な設定はありません。空でないフロンティアは、構成によって少なくとも1つの構成を保持することが保証されます。これは、ロードマップ内の他の構成と比較して、接続されたワークスペースを介して比較的近くにあります。

The worst case complexity for locating the limited frontier occurs when there are no configurations in the roadmap. In this case, the search executes a complete single-source shortest paths algorithm over the entire set of cells reachable from c in the decomposition graph. This may be expensive initially, but as the roadmap coverage of free space increases, it is more and more likely that F will represent a topolog- ically relevant neighborhood. The limited frontier can also be cached for methods which do not delete vertices from the roadmap, and can be updated in linear time on each reuse. As such, the filter’s efficiency and efficacy improve as the

  • ロードマップに設定がない場合、限られた境界を見つけるための最悪のケースの複雑さが発生します。この場合、検索は、分解グラフのcから到達可能なセルのセット全体に対して、完全な単一ソースの最短パスアルゴリズムを実行します。これは最初は高価になるかもしれませんが、空き領域のロードマップカバレッジが増加するにつれて、Fが位相的に関連のある近隣を表す可能性がますます高くなります。限られたフロンティアは、ロードマップから頂点を削除しないメソッドのためにキャッシュすることもでき、再利用ごとに線形時間で更新することができます。このように、フィルタの効率と効

Nonetheless, it is pertinent to choose a fairly coarse de- composition to minimize the cost of the candidate cell search. Extremely fine decompositions provide more stratification of neighborhoods than is needed for the filter, and offer little benefit in return for the additional overhead. A good heuristic is to choose a convex decomposition that generates the smallest number of well-formed cells needed to cover the environment.

  • それにもかかわらず、候補セル検索のコストを最小にするためにかなり粗い構成を選択することは適切である。極端に細かい分解は、フィルタに必要とされるよりも多くの近隣の層別化を提供し、追加のオーバーヘッドと引き換えにほとんど利益を提供しない。優れたヒューリスティックは、環境をカバーするのに必要な最小数の整形式セルを生成する凸型分解を選択することです。
F. Query Relevance

For tree-based methods, choosing neighbors that are rel- evant to solving the query is equally important because performance depends on choosing cells that are likely to generate productive extensions from an “earlier” region of the problem (i.e., closer to the query start) towards a “later” region (i.e., closer to the query goal). We refer to candidate cells meeting this criteria as “query relevant”.

  • ツリーベースのメソッドでは、パフォーマンスは問題の「早い」領域から生産的な拡張を生成する可能性が高いセルを選択することに依存するため、クエリーの解決に関連する隣接要素の選択も同様に重要です。 )「後の」領域に向かって(すなわち、クエリの目標により近い)。この基準を満たす候補セルを「クエリ関連」と呼びます。

The filter can be adjusted to consider the query relevance of potential candidate cells by determining a subset of the original adjacency map for the decomposition graph which discards edges leading away from the goal. This can be computed as a pre-processing step with a single-source shortest paths algorithm starting from the cell which contains the query goal. The resulting distances (which we will call scores) are a measure of each cell’s proximity to the goal through connected workspace: smaller scores indicate closer proximity. Adding the cross-edges creates an adjacency map where each cell’s successors are of equal or greater distance from the query (Alg. 4).

  • ゴールから離れているエッジを捨てる分解グラフのためのオリジナルの隣接マップのサブセットを決定することによって、潜在的な候補セルのクエリ関連性を考慮するようにフィルタを調整することができる。これは、クエリ目標を含むセルから始まる単一ソース最短経路アルゴリズムによる前処理ステップとして計算することができる。得られた距離(これをスコアと呼びます)は、接続されたワークスペースを介した各セルの目標への近接性の尺度です。スコアが小さいほど、近接性が高いことを示します。クロスエッジを追加すると、各セルの後継者がクエリから等しいかそれ以上の距離にある隣接マップが作成されます(図4)。

The filter will now use this mapping instead of the original when exploring for the sampling frontier. This further limits the frontier to those cells that are “behind” the original cell c relative to the goal to encourage productive extensions. The method could feasibly be applied with other types of adjacency maps for specialized problems.

  • サンプリングフロンティアを探索するとき、フィルタはオリジナルの代わりにこのマッピングを使用します。これは、生産的な拡大を促進するという目標に対して、元のセルcの「後ろ」にあるセルにフロンティアをさらに制限します。この方法は、特殊な問題に対して他のタイプの隣接マップにも適用可能です。

IV. Theoretical intution

In topology, a cover of a topological space U is a collec- tion ui ⊆ U such that ∪ui = U . Our decomposition cells represent a cover C of the free workspace Wf ree where each cell ci ∈ C is convex, and for ca, cb ∈ C, ca ∩ cb 6= ∅ iff ca is adjacent to cb in the decomposition graph G. Thus, the adjacency relationships in G define the 1-neighborhood of each cell ci ∈ C.

  • トポロジーでは、位相空間Uのカバーは集合ui⊂Uであり、∪ui= Uである。我々の分解セルは、各セルc i∈Cが凸である自由作業空間Wf reeのカバーCを表し、caについては、分解グラフGにおいてc bに隣接する場合、 Gにおける隣接関係は、各セルの1-近傍c i∈Cを定義する。

In a sense, G is a coarse chart of Wf ree. This is useful because Wf ree is a reasonable over-estimation of W ∗ f ree = projection of Cf ree into W , so G is also a coarse, approx- imate chart of W ∗ f ree. It is approximate in the sense that it contains all of W ∗ f ree as well as some portions of Wf ree which do not intersect Cf ree. As such, two configurations qa, qb ∈ c for c ∈ C are within some convex neighborhood in our approximation of W ∗ f ree. This is a necessary but not sufficient condition for connecting qa, qb via a straight line in Cf ree: it does not guarantee that qa, qb are connected, but it is a much better estimator than the Euclidean distance kqa − qbk.

  • ある意味では、GはWf reeの粗いチャートです。これは、W f reeがW ∗ f ree = C f reeのWへの射影の妥当な過大推定であるため、GもW ∗ f reeの粗い近似グラフであるため便利です。それは、それがC freeと交差しないW f reeのいくつかの部分と同様にW * f reeの全てを含むという意味で近似的である。そのように、c∈Cに対する2つの構成qa、qb∈cは、W * freeの我々の近似ではある凸近傍内にある。これはCf reeにおいて直線でqa、qbを結ぶための必要条件ですが十分条件ではありません:qa、qbが結ばれることを保証するものではありませんが、ユークリッド距離kqa - qbkよりずっと良い推定量です。

We leverage this heuristic when searching for candidate cells for some sampled configuration qrand: because G is a coarsely approximated chart of W ∗ f ree, the configurations within the candidate cells are approximately the subset of the sampling frontier which are nearest to qrand through W ∗ f ree. The heuristic predicts that these are the most promising configurations for attempting a connection to qrand.

  • いくつかのサンプリングされた構成qrandの候補セルを検索するときにこのヒューリスティックを利用します。GはW ∗ f reeのおおよそ近似されたチャートなので、候補セル内の構成は近似的にW ndを通してqrandに近いサンプリングフロンティアのサブセットです。おれ。ヒューリスティックは、これらがqrandへの接続を試みるための最も有望な構成であると予測します。

V. Applicability

As it is based on a workspace decomposition, the filter is appropriate for problems where the translational components of Cspace play a significant role in feasible solutions. This includes many types of rigid-body motions, but is not directly applicable to problems with degrees of freedom in only orientation or joint space.

  • ワークスペース分解に基づいているため、このフィルタは、Cspaceの並進成分が実行可能なソリューションで重要な役割を果たす問題に適しています。これには多くの種類の剛体運動が含まれますが、方向や関節空間だけの自由度の問題には直接適用できません。

The filter also relies on the assumption that Cspace is locally connected, which holds for many problems in the physical world. It is not expected to perform well in more ab- stract configuration spaces where a workspace decomposition does not represent an interesting submanifold of Cspace. This might be rectified by replacing the workspace decomposition with some other coarse cover of an interesting submanifold of Cspace; this investigatiion is left as future work.

  • このフィルタは、Cspaceがローカルに接続されているという仮定にも依存しています。ワークスペース分解がCspaceの興味深い部分多様体を表していない、より抽象的な構成空間ではうまく機能するとは思われません。これは、ワークスペースの分解をCspaceの興味深いサブ多様体の他の粗いカバーで置き換えることによって修正されるかもしれません。この調査は今後の課題として残されています。

VI. Demonstration

We evaluate the method by comparing nearest-neighbor and planning times for several RRT methods with and without the filter and query relevance. The planners used include RRT [2], SST [4], Dynamic Region-biased RRT [5] (DRB-RRT), SyCLoP [6], and a modified version of SyCLoP for holonomic problems referred to as SyCLoP-holo. These were selected as a spectrum of different levels of heuristic guidance. The unfiltered methods use a brute-force nearest- neighbor search to isolate the gains produced by the filter.

  • 我々は、フィルタとクエリの関連性の有無にかかわらず、いくつかのRRT手法について最近傍と計画の時間を比較することによって、手法を評価します。使用されるプランナには、RRT [2]、SST [4]、動的領域バイアスRRT [5](DRB-RRT)、SyCLoP [6]、およびSyCLoPホロと呼ばれるホロノミック問題用の修正版のSyCLoPがあります。これらは、ヒューリスティックガイダンスのさまざまなレベルのスペクトルとして選択されました。フィルタリングされていない方法は、ブルートフォース最近傍探索を使用して、フィルタによって生成された利得を分離する。

The modified SyCLoP-holo algorithm is a modification of SyCLoP for holonomic problems, in which there are no controls to sample. This variant is identical to the original except that (a) a sampled configuration qrand is used as the growth target as in standard RRT, and (b) once a workspace cell is selected from the discrete lead, we use a traditional neighborhood finder to select qnear from the set of configurations within (rather than using the selection history as in the original method). These changes aim to adapt SyCLoP to holonomic problems while retaining the spirit of the method. Since SyCLoP and SyCLoP-holo are already choosing qnear from a single decomposition cell, it does not make sense to subsequently apply our filter. We have included them for comparison because they also employ a decomposition to locate configurations for extension.

  • 修正されたSyCLoPホロアルゴリズムはホロノミック問題のためのSyCLoPの修正であり、そこではサンプリングするための制御がない。 (a)標準RRTのようにサンプリングされたコンフィギュレーションパラメータを成長ターゲットとして使用し、(b)離散リードからワークスペースセルを選択したら、従来の近傍ファインダを使用して選択する点を除いて、この変形はオリジナルと同じです。 (元の方法のように選択履歴を使用するのではなく)内の一連の構成から入手してください。これらの変更は、メソッドの精神を保ちながらSyCLoPをホロノミック問題に適応させることを目的としています。 SyCLoPとSyCLoP-holoはすでに単一の分解セルから適切な方法を選択しているので、後でフィルタを適用することは意味がありません。それらはまた、拡張のための構成を見つけるために分解を使用するので、それらを比較のために含めた。
A. Experimental setup

We use four simulated environments for the evaluation with different aspects of interest (Fig. 3). Helico is rel- atively open. LTunnel presents three narrow entrances. Garage has a four-story winding ramp and additional longer routes toward the other end of the environment. The GridMaze environment has long, winding paths in a

  • 評価には、4つの異なるシミュレーション環境を使用します(図3)。 Helicoは比較的オープンです。 LTunnelは3つの狭い入り口を提示します。ガレージには4階建ての曲がりくねった傾斜路があり、環境の反対側に向かってさらに長いルートがあります。 GridMaze環境には、長い曲がりくねった道があります。

cramped tunnel that constrains the robot’s rotational DOFs. Maze-like problems are notoriously difficult for RRT’s be- cause the sampled target configurations qrand are quite frequently located across the maze walls, resulting in short, erratic extensions that scrape very close to the obstacle space. Additionally, corners and tight turns frequently create portions of Cspace where only a very small portion of the local sampling volume can yield a configuration that extends the tree around the corner.

  • ロボットの回転自由度を制限する窮屈なトンネル。迷路のような問題は、サンプリングされたターゲット構成が迷路の壁を横切って頻繁に配置されているためにRRTにとって非常に困難であり、その結果、障害空間のすぐ近くを削り取っている。さらに、コーナーと狭い曲がりは、Cspaceの一部を頻繁に作成します。そこでは、ローカルサンプリングボリュームのごくわずかな部分だけが、コーナーの周りにツリーを拡張する設定を生成できます。

Nonholonomic trials were performed in the Helico and LTunnel environments. Nonholonomic robots increase the problem difficulty by increasing the dimensions of the plan- ning space and severely limiting the allowed actions to the robot’s control set.

  • 非ホロノミック試験は、HelicoおよびLTunnel環境で行われました。非ホロノミックロボットは、計画スペースの寸法を大きくし、許容される動作をロボットの制御セットに厳しく制限することによって、問題を難しくします。

The robots in all cases are 6 DOF rigid bodies. The RRT maximum extension distance is set to approximately the bounding sphere radius for the robot, and a tetrahedralization is used for the workspace decomposition. The nonholonomic robots are fully actuated with simple discrete control sets (i.e., over a single extension the robot can exert a force on itself in any one of its position or orientation DOFs). An even mix of best and random controls were used for RRT, SST, and DRB-RRT, while random controls were used for SyCLoP (as it does not use a growth target).

  • すべての場合のロボットは6自由度の剛体です。 RRTの最大延長距離は、ロボットの境界球半径にほぼ設定され、四面体化がワークスペース分解に使用されます。非ホロノミックロボットは、単純な個別制御セットを用いて完全に作動される(すなわち、単一の伸長にわたって、ロボットは、その位置または向きDOFのうちのいずれか1つでそれ自体に力を及ぼすことができる)。 RRT、SST、およびDRB-RRTには、ベストコントロールとランダムコントロールを均等に組み合わせて使用​​しましたが、SyCLoPにはランダムコントロールを使用しました(増殖ターゲットを使用しないため)。

All methods were implemented in a C++ motion planning library developed in the Parasol Lab at Texas A&M Univer- sity, which uses a distributed graph data structure from the Standard Template Adaptive Parallel Library (STAPL) [15], a C++ library designed for parallel computing. The workspace tetrahedralization was performed with a combination of the TetGen [16] and CGAL [17] libraries.

  • すべての方法は、テキサスA&M大学のParasol Labで開発されたC ++動作計画ライブラリで実行されました。これは、並列計算用に設計されたC ++ライブラリであるSTAPL [15]からの分散グラフデータ構造を使用します。 。 TetGen [16]とCGAL [17]ライブラリを組み合わせて、ワークスペースの四面体化を実行しました。

All experiments were executed on a desktop computer running CentOS 7 with an Intel R(cid:13) Core 2 Quad Q9550 CPU at 2.83 GHz, 8 GB of RAM, and the GNU g++ compiler version 4.8.5.

  • すべての実験は、2.83 GHzのIntel R(cid:13)Core 2 Quad Q9550 CPU、8 GBのRAM、およびGNU g ++コンパイラバージョン4.8.5を搭載したCentOS 7を実行しているデスクトップコンピュータで実行しました。

Thirty-five trials are run for each evaluation. Each run is limited to a maximum time of three minutes to complete the queries illustrated in Fig. 3. Executions which do not solve the query in this time are considered failures. We report the success rate for each planner and the average execution and nearest-neighbor times for the successful runs (Fig. 4). Error bars indicate standard deviation in all cases. Statistical significance is measured with Welch’s t-test on the successful trials.

  • 評価ごとに30回の試行が行われます。各実行は、図3に示すクエリを完了するのに最大3分の時間に制限される。この時間内にクエリを解決しない実行は失敗と見なされる。各プランナーの成功率と、成功した実行の平均実行時間と最近隣時間を報告します(図4)。エラーバーは全ての場合において標準偏差を示す。統計的有意性は、成功した試験に関するウェルチのt検定で測定されます。

The reported run times do not include the time needed to decompose the workspace; the slowest environment to decompose is the Garage, which takes about one second.

  • 報告された実行時間には、ワークスペースの分解に必要な時間は含まれていません。最も遅い分解環境はガレージで、これには約1秒かかります。
Analysis

Topological Filter: A consistent drop in nearest-neighbor time is observed for all planners when using the topological filter without query relevance (in both holonomic and non- holonomic trials). The difference from the unfiltered method is highly significant (pval ≤ .01) in all cases except DRB- RRT in GridMaze (pval = .05).

  • トポロジカルフィルタ:クエリの関連性なしにトポロジカルフィルタを使用すると(ホロノミックおよび非ホロノミックトライアルの両方で)、すべてのプランナで最近傍時間が一貫して減少します。フィルタリングされていない方法との違いは、GridMazeのDRB-RRT(pval = .05)を除くすべての場合において非常に重要です(pval = 0.01)。

The effect on overall planning time is positive with high confidence (pval ≤ .01) in the holonomic trials, excepting

  • 全体的な計画時間に対する影響は、ホロノミック試行における高い信頼度(pval≦0.01)ではプラスですが、例外はあります。

Fig. 3. Test environments and (robots). Selected paths from RRT with filtering are shown from start (green) to goal (red).
- 図3テスト環境と(ロボット)フィルタリングを伴うRRTからの選択された経路は、スタート(緑)からゴール(赤)まで示されています。

DRB-RRT in GridMaze (improvement with pval = .08). In the other cases, significant improvements are observed in both total time and variance. In the nonholonomic trials, planning time improved with high confidence (pval ≤ .01) for SST in both environments and RRT in LTunnel. The other three cases showed low confidence improvements.

  • GridMazeにおけるDRB-RRT(pval = .08での改善)それ以外の場合は、合計時間と分散の両方で大幅な改善が見られます。非ホロノミック試行では、両方の環境でのSSTとLTunnelでのRRTの高い信頼性(pval≤0.01)で計画時間が改善されました。他の3つのケースは、信頼度の改善が低かった。

The unguided planners RRT and SST also attained a unilateral increase in success rate, and are able to reliably solve the holonomic GridMaze and Garage problems within the three minute time limit. The guided planner DRB- RRT sees equivalent or better success rate in all cases.

  • 無人計画立案者RRTとSSTも成功率の一方的な増加を達成し、そして3分の制限時間内にホロノミックGridMazeとGarage問題を確実に解決することができます。ガイドプランナーDRB-RRTは、すべてのケースで同等またはそれ以上の成功率を見ています。

Query Relevance: The query relevance option presents mixed results for both nearest-neighbor and planning time. The nearest neighbor time is frequently worse compared with the plain filter. In Helico, small differences are seen for all planners with high confidence (pval ≤ .01) except RRT (pval = .90) and nonholonomic DRB-RRT (pval = .12). In holonomic LTunnel, all methods require more nearest- neighbor time than the plain filter with high confidence (pval ≤ .01) except SST (pval = .77). The nonholonomic LTunnel shows low confidence differences across the board (pval ≥ .23). In GridMaze, all planners showed low confidence differences (pval ≥ .43). In Garage, RRT and SST used significantly less nearest-neighbor time with query relevance (pval ≤ .01), while DRB-RRT showed a high confidence increase (pval ≤ .01).

  • クエリ関連性:クエリ関連性オプションは、最近隣時間と計画時間の両方について混在した結果を表示します。最近隣時間は、通常のフィルターに比べて悪いことがよくあります。 Helicoでは、RRT(pval = .90)と非ホロノミックDRB-RRT(pval = .12)を除いて、信頼度が高い(pval≤0.01)すべてのプランナーに小さな違いが見られます。ホロノミックLTunnelでは、SST(pval = .77)を除いて、すべての方法が高い信頼性(pval≤0.01)を持つ単純なフィルターより多くの最近傍時間を必要とします。非ホロノミックLTunnelは、ボード全体で低い信頼度の差を示します(pval≧0.23)。 GridMazeでは、すべての計画者が低い信頼度の差を示しました(pval≧0.43)。 Garageでは、RRTとSSTはクエリ関連性を持つ最短隣接時間(pval≤0.01)を使用しましたが、DRB-RRTは高い信頼性増加(pval≤0.01)を示しました。

The overall planning time with the query relevance option is frequently worse than the regular filter, with the most extreme cases occuring for the guided planner DRB-RRT. The holonomic Helico trials were mixed: RRT showed a low confidence degredation (pval = .27), SST showed a high confidence improvement (pval ≤ .01), and DRB- RRT showed a high confidence degredation (pval ≤ .01). The nonholonomic trials exhibited the opposite trend: RRT and DRB-RRT improved with low confidence (pval ≥ .69) while SST degraded with high confidence (pval ≤ .01). In holonomic LTunnel we see a unilateral increase in

  • 照会関連オプションを使用した全体的な計画時間は、通常のフィルターよりも悪いことが多く、ガイド付きプランナーのDRB-RRTが最も極端な場合です。ホロノミックHelico試験を混合した:RRTは低い信頼度の低下を示し(pval = 0.27)、SSTは高い信頼度の改善を示し(pval≦0.01)、そしてDRB-RRTは高い信頼度の低下を示した(pval≦0.01)。非ホロノミック試験は反対の傾向を示した:RRTおよびDRB-RRTは低い信頼度(pval≧0.69)で改善したが、SSTは高い信頼度(pval≦0.01)で悪化した。ホロノミックLTunnelでは、一方的な増加が見られます。

planning time for all planners, with low confidence for SST (pval = .73) and high confidence for RRT and DRB-RRT (pval ≤ .01). In the nonholonomic version RRT attained a slight improvement but with very low confidence (pval = .91), while the other two planners again degraded with low confidence (pval ≥ .29). In GridMaze, the planning time increased over the regular filter with high confidence for RRT (pval ≤ .01) and low confidence for SST and DRB-RRT (pval = .2 and pval = .03, respectively). In Garage, RRT and SST saw large improvements while DRB-RRT performed worse, with high confidence (pval ≤ .01) in all cases.

  • SSTに対する信頼度が低く(pval = 0.73)、RRTおよびDRB-RRTに対する信頼度が高い(pval≦0.01)、すべての計画者の計画時間。非ホロノミック版では、RRTはわずかな改善を達成したが、非常に低い信頼度(pval = .91)で、他の2人の計画者は再び低い信頼度(pval = .29)で劣化した。 GridMazeでは、RRTに対する信頼度が高く(pval≦0.01)、SSTおよびDRB-RRTに対する信頼度がそれぞれ低い(それぞれpval = 0.2およびpval = 0.03)ため、計画時間は通常のフィルターよりも長くなりました。 Garageでは、RRTとSSTは大幅に改善されましたが、DRB-RRTは、すべてのケースで高い信頼性(pval≤0.01)で悪化しました。

Success rate with query relevance was roughly equivalent to the regular filter in most cases. Reductions are observed for RRT in GridMaze, DRB-RRT in Garage, and SST in the nonholonomic LTunnel.

  • クエリに関連性のある成功率は、ほとんどの場合、通常のフィルタとほぼ同等でした。 GridMazeではRRT、GarageではDRB-RRT、非ホロノミックLTunnelではSSTの減少が見られます。

The SyCLoP planner shows a small amount of nearest- neighbor time because we attempt to connect configurations which are very near to the goal directly; we found this to necessary in practice to obtain reasonable results. In the nonholonomic Helico, SyCLoP wastes some effort evenly expanding the tree; however the LTunnel results show that this method is highly effective in less expansive environments.

  • SyCLoPプランナーは、ゴールに非常に近い構成を直接接続しようと試みるため、少量の最近傍時間を表示します。合理的な結果を得るためには、実際にこれが必要であると判断しました。非ホロノミックHelicoでは、SyCLoPはツリーを均等に拡張するためにいくらかの努力を浪費します。ただし、LTunnelの結果から、この方法はそれほど拡張性のない環境では非常に有効であることがわかります。
C. Discussion

The nearest-neighbor time for the query relevance variant is generally worse than for the plain topological filter because the more restrictive filter returns no candidates with higher probability, and therefore requires more attempts over the entire execution. For DRB-RRT, this restrictiveness appears to interfere with the guidance heuristic in many cases. In these scenarios, the query relevance is filtering out candidates that were expected by the guidance heuristic. Specifically, DRB-RRT employs moving sampling regions from which new samples are drawn; if the sampling regions are moving perpendicular to the flow prescribed by query relevance, this creates contention where the filter could reject the nearby

  • より限定的なフィルタはより高い確率で候補を返さず、したがって実行全体にわたってより多くの試行を必要とするため、クエリ関連性バリアントの最近傍時間は通常、単純なトポロジカルフィルタよりも悪い。 DRB-RRTでは、この制限がガイダンスヒューリスティックを妨げると思われます。これらのシナリオでは、クエリの関連性がガイダンスヒューリスティックによって予想された候補を除外しています。具体的には、DRB − RRTは新しいサンプリングがそこから引き出される移動サンプリング領域を使用する。サンプリング領域がクエリ関連性によって規定されたフローに対して垂直に移動している場合、これは、フィルタが近くのフィルタを拒否する可能性がある場合に競合を生じさせる。

Fig. 4. Holonomic experiment results, including average execution and nearest-neighbor times for the trials which solved the query within three minutes, and success rate out of thirty-five trials. Error bars indicate standard deviation. A * indicates that no trials were successful. SyCLoP refers to SyCLoP-holo.

  • 図4 3分以内にクエリを解決した試行の平均実行時間と最近隣時間、および30回の試行のうち成功率を含むホロノミック実験の結果。エラーバーは標準偏差を示す。 *は試験が成功しなかったことを示します。 SyCLoPとはSyCLoP-holoのことです。

Fig. 5. Nonholonomic experiment results, including average execution and nearest-neighbor times for the trials which solved the query within three minutes, and success rate out of thirty-five trials. Error bars indicate standard deviation. A * indicates that no trials were successful.

  • 図5 3分以内にクエリを解決した試行の平均実行時間と最近隣時間、および30回の試行のうち成功率を含む、非ホロノミック実験の結果。エラーバーは標準偏差を示す。 *は試験が成功しなかったことを示します。

configurations as not en route to the query relative to the sampling region.

  • サンプリング領域に関連したクエリへの途中ではない構成。

For the unguided planners RRT and SST, the filters provide an immense boost in both efficiency and reliability in all cases. The query relevance variant produced good results in Garage for these planners, but did not perform well with DRB-RRT. Based on this observation, query relevance appears to be a potentially useful enhancement only for unguided planners.

  • ガイドなしプランナーのRRTとSSTにとって、フィルターはすべての場合において効率と信頼性の両方において非常に大きな向上をもたらします。クエリ関連性バリアントは、これらのプランナに対してGarageで良好な結果をもたらしましたが、DRB-RRTではうまく機能しませんでした。この観察に基づいて、クエリの関連性は、ガイドなしプランナーにのみ有用な可能性がある拡張機能のように思われます。

The filter is also shown to work in nonholonomic problems with reduced efficacy. The most important gains are in terms of the success rates in the LTunnel environment, where the filter helps limit the number of unproductive extensions.

  • フィルタは、効力が低下した非ホロノミック問題でも機能することが示されています。最も重要な利点は、フィルタが生産的でない拡張の数を制限するのに役立つLTunnel環境での成功率です。

VII. Conclusion

We present a topological filter for nearest-neighbor queries which selects candidate neighbors that are nearby through connected workspace. The filter identifies candidates using a graph search through a workspace decomposition graph, and subsequently presents a significantly reduced set of candidate neighbors to the nearest-neighbor algorithm used by a sampling-based planner.

  • 接続ワークスペースを介して近くにある候補近隣者を選択する最近傍照会のための位相フィルタを提示します。フィルタは、ワークスペース分解グラフによるグラフ検索を使用して候補を識別し、続いて、サンプリングベースのプランナによって使用される最近傍アルゴリズムに対して、大幅に縮小された候補の近隣の集合を提示する。

The topological filter demonstrates promise as a method for candidate neighbor reduction. The data shows that it improves the nearest-neighbor time significantly in our test cases, and that the query relevance option can provide additional performance boosts for unguided planners.

  • トポロジカルフィルタは、候補近隣削減のための方法としての見込みを示している。データは、それが我々のテストケースにおいて最近傍時間を大幅に改善すること、そしてクエリ関連性オプションがガイドされていない計画者にさらなるパフォーマンス向上を提供できることを示しています。

Since our method is a filtering pre-step for some other nearest-neighbor algorithm, it may be possible to combine it synergistically with fast computational methods such as kd- trees or locality-sensitive hashing. We leave this investigation as future work.

  • 我々の方法は他の最近傍アルゴリズムのためのフィルタリング前段階であるので、それをkd木または局所性に敏感なハッシングのような速い計算方法と相乗的に組み合わせることが可能であるかもしれない。この調査は将来の作業として残します。