適当工学論文和訳 #01 The Vector Field Histogram – Fast Obstacle Avoidance for Mobile Robots

気になった論文を自分のために適当に和訳して載せるクソコーナー。
内容把握が優先で、重要じゃないところはガンガン省略するので注意されたし。

論旨優先で式や変数の説明部分をバッサリカットする都合、原文の引用がキモかったり、そもそも訳文としてクソ以下の代物なので、これを何かの参考にすると痛い目を見る。
必ず原文のPDFを横において読むこと。

今回の論文は、
“Johann Borenstein, Member, IEEE, and Yoram Koren, Senior Member, IEEE”, “The Vector Field Histogram – Fast Obstacle Avoidance for Mobile Robots”, IEEE Transactions on Robotics and Automation, Vol. 7, No. 3, June 1991, pp.278 – 288.

オリジナルのPDFはここ

ベクトル場ヒストグラム法という、ロボットの経路計画アルゴリズムで、Wikipediaの記事も存在する有名なものらしい。Google Scalarで調べたこの記事の執筆時点での被引用数は2598。すごい(小並感)。
同じ著者によるVFH+なる発展形のアルゴリズムも存在するらしいが、ひとまずは基礎となった論文を読んでいく。

Abstract

A new real-time obstacle avoidance method for mobile robots has been developed and implemented. This method, named the vector field histogram (VFH), permits the detection of unknown obstacles and avoids collisions while simulateneously steering the mobile robot toward the target.

移動ロボットのための新しいリアルタイム障害物回避法が開発され、実施されている。この方法は、ベクトル場ヒストグラム(VFH)と呼ばれており、未知の障害物の検出を可能にし、衝突を回避しながら移動ロボットを標的に向かって操縦する。

The VFH method uses a two-dementional Cartesian histogram grid as a world model. This world model is updated continuously with range data sampled by on-board range sensors. The VFH method subsequently employs a two-stage datareduction process in order to compute the desired control commands for the vehicle.

VFH法は、2次元直交座標系のヒストグラムグリッドを外部環境モデルとして使用する。この外部環境モデルは、オンボードの測距センサによってサンプリングされた距離データで絶えず更新されている。その後、VFH法は、車両にとって望ましい制御コマンドを計算するために、2段階のデータ供給プロセスを採用する。

In the first stage the histogram grid is reduced to a one-dimensional polar histogram that is constructed around the robot’s momentary location. Each sector in the polar histogram contains a value representing the polar obstacle density in that direction.

第1段階では、ヒストグラムグリッドは、ロボットの瞬間的な位置の周囲に構築された1次元極座標ヒストグラムに縮小される。極座標ヒストグラムの各セクタには、その方向の極限障害物密度を表す値が含まれている。

In the second stage, the algorithm selects the most suitable sector from among all polar histogram sectors with a low polar obstacle density, and the steering of the robot is aligned with that direction. Experimental results from a mobile robot traversing densely cluttered obstacle courses in smooth and continuous motion and at an average speed of 0.6-0.7 m/s demonstrate the power of the VFH method.

第2段階では、極性障害物密度の低いすべての極ヒストグラムセクタの中から最適なセクタを選択し、ロボットの操舵をその方向に合わせる。移動ロボットが高密度に障害物が散乱したコースを滑らかで連続的に移動し、平均速度0.6~0.7m / sで移動することによる実験結果はVFH法の有効性を示している。

1. Introduction

Obstacle avoidance is one of the key issues to successful applications of mobile robot systems.

障害物回避は、移動ロボットシステムのアプリケーションの成功への重要な課題の1つである。

All mobile robots feature some kind of collision avoidance, ranging from primitive algorithms that detect an obstacle and stop the robot short of it in order to avoid a collision through sophisticated algorithms that enable the robot to detour obstacles.

すべての移動ロボットは、障害物を検出する原始的なアルゴリズムや、障害物を迂回することができる高度なアルゴリズムなどの、ある種の衝突回避機能を持っている。

The latter algorithms are much more complex, since they involve not only the detection of an obstacle, but also some kind of quantitative measurements concerning the dimensions of the obstacle.

後者のアルゴリズムは、障害物の検出だけでなく、障害物の寸法に関する何らかの定量的測定も伴うため、前者に比べはるかに複雑である。

Once these have been determined, the obstacle avoidance algorithm needs to steer the robot around the obstacle and proceed toward the original target.

一度これらが決定されると、障害物回避アルゴリズムは、障害物の周りでロボットを操舵し、目標地点に向かって進む必要がある。

Usually, this procedure requires the robot to stop in from of the obstacle, take the measurements, and only then resume motion.

通常、この手順では、ロボットが障害物から立ち止まって測定を行い、その後で動きを再開する必要がある。

Obstacle avoidance (also called reflexive obstacle avoidance or local path planning) may result in nonoptimal paths[5] since no prior knowledge about the environment is used.

障害物の回避(反射的障害物回避またはローカルパスプランニングとも呼ばれる)は、環境に関する事前の知識を利用していないため、最適でない経路[5]をもたらす可能性がある。

A brief survey of relevant earlier obstacle avoidance methods is presented in Section II, while Section III summarizes the virtual force field (VFF), an obstacle-avoidance method developed earlier by our group at the University of Michigan [5].

関連する初期の障害物回避方法の簡単な調査は2節に示され、3節はミシガン大学で以前に開発された障害回避方法である仮想力場(VFF)を要約している。

While the VFF method provides superior real-time obstacle avoidance for fast mobile robots, some limitations concerning fast travel among densely cluttered obstacles were identified in the course of our experimental work [18].

VFF法は高速移動ロボットにとって優れたリアルタイム障害物回避を提供するが、密集した障害物の間を速く移動することに関するいくつかの制限が我々の実験作業の過程で同定された。

To overcome these limitations, we developed a new method, named vector field histogram (VFH), which is introduced in Section IV.

これらの限界を克服するために、我々は4節で導入したベクトル場ヒストグラム(VFH)という新しい方法を開発した。

The VFH method eliminates the shortcomings of the VFF method, yet retains all the advantages of its predecessor (as will be shown in Section IV).

VFH法はVFF法の欠点を排除するが、(4節で示されるように)その前身のすべての利点を保持する。

A comparison of the VFH method to earlier methods is given in Section V, and Section VI presents experimental results obtained with our VFH-controller mobile robot.

VFH法と従来の方法の比較は5節に示し、6節ではVFHコントローラ移動ロボットで得られた実験結果を示す。

2. Survey of Earlier Obstacle-Avoidance Methods

This section summarizes relevant obstacle avoidance methods, namely edge-detection, certainty grids, and potential field methods.

この節では、関連する障害回避手法、つまりエッジ検出、Certainty Grid(訳注:日本語圏での名前が分からん)、ポテンシャル法を要約する。

2.A Edge-Detection Methods

One popular obstacle avoidance method is based on edgedetection.

この一般的な障害物回避方法はエッジ検出に基づいている。

In this method, an algorithm tries to determine the position of the vertical edges of the obstacle and then steer the robot around either one of the “visible” edges.

この方法では、アルゴリズムが障害物の垂直エッジの位置を決定し、ロボットを「目に見える」エッジのいずれかで操舵しようとする。

The line connecting two visible edges is considered to represent one of the boundaries of the obstacle.

2つの目に見えるエッジを結ぶ線は、障害物の境界の1つを表すと考えられる。

This method was used in our very early research [4], as well as in several other works [11], [21], [22], [28], all using ultrasonic sensors for obstacle detection.

この方法は、我々の過去の研究において利用されており、すべての研究で超音波センサを障害物回避に利用した。

A disadvantage with current implementations of this method is that the robot stops in front of obstacles to gather sensor information.

この方法の現在の実装の欠点は、ロボットが障害物の前で停止してセンサ情報を収集することである。

However, this is not an inherent limitation of edge-detection methods; it may be possible to overcome this problem with faster computers in future implementations.

しかしながら、これはエッジ検出方法の固有の制限ではない。将来の実装で高速なコンピュータでこの問題を克服することは可能かもしれない。

今のコンピュータのパワーなら多分楽勝。

In another edge-detection approach (using ultrasonic sensors), the robot remains stationary while taking a panoramic scan of its environment [13], [14].

別のエッジ検出アプローチ(超音波センサを使用)では、ロボットはその環境のパノラマスキャンを行う間は静止している。

After the application of certain line-fitting algorithms, an edge-based global path planner is instituted to plan the robot’s subsequent path.

特定の線フィッティングアルゴリズムを適用した後、エッジベースのグローバルパスプランナを導入して、ロボットの後続パスを計画する。

A common drawback of both edge-detection approaches is their sensitivity to sensor accuracy.

両方のエッジ検出手法の共通の欠点は、センサ精度への感度である。

Ultrasonic sensors present many shortcomings in this respect: Poor directionality limits the accuracy in determining the spatial position of an edge to 10-50 em, depending on the distance to the obstacle and the angle between the obstacle surface and the acoustic axis.

超音波センサは、この点で多くの欠点を有する。方向性が悪いと、障害物までの距離および障害物表面と音響軸との間の角度に応じて、エッジの空間位置の精度が10〜50cmに制限される。

Frequent misreadings are caused by either ultrasonic noise from external sources or stray reflections from neighboring sensors (i.e., crosstalk).

頻繁な誤読は、外部ソースからの超音波ノイズまたは隣接するセンサからの迷光(すなわち、クロストーク)のいずれかによって引き起こされる。

Misreadings cannot always be filtered out, and they cause the algorithm to falsely detect edges.

誤読が常に除外されるとは限らず、アルゴリズムが誤ってエッジを検出する原因となる。

Specular reflections occur when the angle between the wavefront and the normal to a smooth surface is too large.

鏡面反射は、波面と滑らかな面の法線との間の角度が大きすぎる場合に発生する。

In this case the surface reflects the incoming ultrasound waves away from the sensor, and the obstacle is either not detected or is “seen” as much smaller than it is in reality (since only part of the surface is detected).

この場合、表面はセンサから遠ざかる入射超音波を反射し、障害物は実際には検出されないか、または実際にはそれよりも小さく見える(表面の一部のみが検出されるため)。

Any one of these errors can cause the algorithm to determine the existence of an edge at a completely wrong location, often resulting in highly unlikely paths.

これらのエラーのいずれかにより、完全に間違った位置にエッジが存在するかどうかをアルゴリズムが判断する可能性があり、結果として経路がほとんどない可能性がある。

2.B The Certainty Grid for Obstacle Representation

省略

2.C Potential Field Methods

省略

3. The Virtual Force Field Method

省略

4. The Vector Field Histogram Method

Careful analysis of the shortcomings of the VFF method reveals its inherent problem: excessively drastic data reduction occurs when the individual repulsive forces from histogram grid cells are totaled to calculate the resultant force vector Fr.

VFF法の欠点を慎重に分析すると、その固有の問題が明らかになる。ヒストグラムグリッドセルからの個々の反発力を合計して合力ベクトル F_r を計算すると、過度に劇的なデータ減少が起こることである。

Hundreds of data points are reduced in one step to only two items: the direction and the magnitude of Fr. Consequently, detailed information about the local obstacle distribution is lost.

何百ものデータ点が1つのステップで2つのアイテム、すなわち F_r の方向と大きさにのみ減少する。その結果、局所障害物分布に関する詳細情報が失われる。

To remedy this shortcoming, we have developed a new method called the vector field histogram (VFH).

この欠点を改善するために、我々はベクトル場ヒストグラム(VFH)と呼ばれる新しい方法を開発した。

The VFH method employs a two-stage data-reduction technique, rather than the single-step technique used by the VFF method. Thus, three levels of data representation exist:

VFH法は、VFF法で使用されるシングルステップ技術ではなく、2段階のデータ削減技術を採用している。したがって、3つのレベルのデータ表現が存在する。

1) The highest level holds the detailed description of the robot’s environment. In this level, the two-dimensional Cartesian histogram grid C is continuously updated in real time with range data sampled by the on-board range sensors. This process is identical to the one described in Section III for the VFF method.

1) 最も高いレベルは、ロボットの外部環境の詳細な説明を保持する。このレベルでは、2次元直交座標系ヒストグラムグリッド C は、測距センサによってサンプリングされた距離データでリアルタイムに連続的に更新される。この工程は、VFF法の3節で説明したものと同じである。

2) At the intermediate level, a one-dimensional polar histogram H is constructed around the robot’s momentary location. H comprises n angular sectors of width ex. A transformation (described in Section IV-A below) maps the active region C* onto H, resulting in each sector k holding a value h k that represents the polar obstacle density in the direction that corresponds to sector k.

中間レベルでは、ロボットの瞬間的な位置の周りに1次元極ヒストグラム H が構築される。 H は、幅 α の n 個の角度セクタを含む。 変換(以下の節4-Aに記載)は、活性領域 C* を H にマッピングし、各セクタ k は、セクタ k に対応する方向の極障害物密度を表す値 h_k を保持する。

平面レーザスキャナでデータを計測している場合は、そもそもこの段階のデータが直接得られることになるんだろうか。

3) The lowest level of data representation is the output of the VFH algorithm: the reference values for the drive and steer controllers of the vehicle. The following sections describe the two data-reduction stages in more detail.

データ表現の最低レベルは、VFHアルゴリズムの出力である。出力は、車両のドライブおよびステアリングコントローラの基準値です。次のセクションでは、2つのデータ削減段階について詳しく説明する。

4.A First Data Reduction and Creation of the Polar Histogram

訳注:引用中の数式はLaTeX風に書き換えた。あくまで「LaTeX風」であって、\starとかはそのままだったりする。

The first data-reduction stage maps the active region C* of the histogram grid C onto the polar histogram H, as follows: As with our earlier VFF method, a window moves with the vehicle, overlying a square region of w_s x w_s cells in the histogram grid (see Fig. 4).

第1のデータ削減段階では、次のように、ヒストグラムグリッド C のアクティブ領域 C* を極座標系ヒストグラム H に写像する。先のVFF法と同様に、ウインドウは w_s \times w_s セルの正方形領域 ヒストグラムグリッド(図4参照)である。

The contents of each active cell in the histogram grid are now treated as an obstacle vector, the direction of which is determined by the direction β from the cell to the vehicle center point (VCP) (訳注:式を省略) and magnitude is given by (訳注:式を省略).

ヒストグラムグリッド内の各アクティブセルの内容は、障害ベクトルとして扱われ、その方向は、セルから車両中心点(VCP)への方向 β (訳注:式を省略) および (訳注:式を省略) によって与えられるマグニチュードによって決定される。

1) C*_{i,j} is squared. This expresses our confidence that recurring range readings represent actual obstacles, as opposed to single occurrences of range readings, which may be caused by noise.

C*_{i、j}は2乗される。 これは、雑音によって引き起こされる可能性のある距離測定値の単一の発生とは対照的に、反復的な距離測定値が実際の障害物を表すという自信を表している。

ちょっとここの訳が上手く出来ない。
recurring は繰り返しでも反復でもなくて、もしかして2乗の事を指しているんだろうか?

2) m_{i,j} is proportional to -d. Therefore, occupied cells produce large vector magnitudes when they are in the immediate vicinity of the robot and smaller ones when they are further away. Specifically, a and b are chosen such that a – bd_{max} = 0, where d_{max} = \sqrt{2}(w_s – 1)/2 is the distance between the farthest active cell and the VCP. This way m_{i,j} = 0 for the farthest active cell and increases linearly for closer cells.

m_ {i、j} は -d に比例する。したがって、占有されたセルは、ロボットのすぐ近くにあるときに大きなベクトルの大きさを生成し、遠くにあるときには小さなベクトルを生成する。 特に、aおよびbは、a – bd_{max} = 0 となるように選択され、d_{max} = \sqrt{2}(w_s – 1)/2 は、最も遠いアクティブセルとVCPとの間の距離である。このようにして、最も遠いアクティブセルの m_{i、j} = 0 となり、より近いセルの場合は線形に増加する。

ここの訳もめちゃくちゃ。言いたいことは分かるんだが、どうも数式を並べずに論文を訳そうと言うのが、どだい無理な話だったか。
ちゃんと元の論文をと見比べながら読んで欲しい。

ここで飽きた。続きはまた気が向いた時に。

5. Comparison to Earlier Methods

省略

6. Experimental Results

省略

7. Conclusions

省略