グリッド環境におけるヒューリスティック探索アルゴリズムのパフォーマンス指標

3 実験環境とパフォーマンス指標

ヒューリスティック探索アルゴリズムは、出発地と目的地の位置が与えられたときに最適な経路を決定するため、ロボットの経路探索などの分野で重要な役割を果たします。グリッドベースの環境は、自律航行やロボット工学など、これらのアルゴリズムを実装できる現実世界の環境シナリオを表現するために一般的に使用されています [6]。本研究では、さまざまなグリッド環境でのよく知られたヒューリスティック探索アルゴリズム、つまり D*、D* Lite、LPA*、LRTA*、RTAA*、および ARA* を包括的に分析します。ユークリッド距離ヒューリスティックを使用してアルゴリズムの検索をガイドし、障害物の密度やグリッドサイズなどのいくつかのグリッド特性がアルゴリズムのパフォーマンスに与える影響を評価します。

私たちの研究では、研究コミュニティのパス計画タスクで一般的に使用されているだけでなく、そのシンプルさと制御の容易さから、グリッドベースの環境を使用しています。グリッドは、通過可能な状態を表す白いセルで構成され、黒いセルは通過不可能な障害物を表します。私たちのシミュレーションのエージェントは、水平および垂直移動のコストが 1、斜め移動のコストが √ 2 で、8 方向に移動できます。ランダムに生成されたグリッド環境とパーソナライズされたグリッド環境の 2 種類のグリッド環境を使用しました。

ランダムに生成されたグリッドベースの環境:グリッドは 3 つのパラメータによって特徴付けられます。

グリッド サイズ (NxN)、障害物の密度、および開始状態と目標状態の間の距離。各パラメータが検索アルゴリズムのパフォーマンスに与える影響を調べるために、他のパラメータを一定に保ちながら、各パラメータを個別に変更しました。バリエーションには、グリッド サイズの変更、開始から目標までの距離の変更、障害物の密度の変更が含まれます。バリエーション内の各グリッドに対して、同じグリッド パラメータの 10 個のランダムなインスタンスを生成しました (たとえば、障害物の密度が 0.25、サイズが 300x300、開始から目標までの距離が 140 のグリッドには、ランダムに生成された 10 個のインスタンスがあります)。

パーソナライズされたグリッド環境:より具体的なシナリオをシミュレートするために設計されています。これらのグリッドは、開始状態と終了状態の両方で固定サイズ (71 x 31 ユニット) と固定位置を持ち、障害物の構成に基づいて 2 つの部分に分割されています。

•水平壁の構成:これらの実験では、グリッド長の 10 単位ごとにグリッド幅の半分の水平壁を追加します。新しく生成されたグリッドでは、左から右への方向と右から左への方向の 2 つの方向に壁を追加しました。

•水平壁の長さの設定:ここでは、配置可能なすべての壁を追加します。

グリッドの長さを変更し、新しいグリッドを生成するたびに、すべての壁の長さを 2 単位ずつ増やします。

私たちは、これら 2 つの異なる環境を採用して徹底的な分析を行い、2 つの異なる妨害シナリオがある場合の検索アルゴリズムのパフォーマンスに関する微妙な洞察を明らかにしようとしました。最初のシナリオでは、障害物がグリッド内にランダムに散在していますが、2 番目のシナリオでは、壁のような構造が、接続された障害物の塊として表示されます。

実験で使用されたさまざまな検索アルゴリズムのパフォーマンスを評価するために、次のメトリックを選択しました。

•パス コスト:このメトリックは、開始から目標状態までのパスの長さまたは実行されたアクションの数を測定します。ソリューションの品質を示します。

•メモリ消費量:アルゴリズムがソリューションを見つけるために必要なメモリ量を測定します。アルゴリズムのスケーラビリティを確認するために重要であり、(KB) 単位で測定されます。

•解決時間:アルゴリズムが解決策を見つけるのにかかる合計時間をミリ秒 (ms) 単位で表します。

実験は、3.30GHz 27 個の Intel i9 コア、250Gb の RAM を搭載し、Ubuntu Linux 22.04 を実行している環境で実施しました。設定は次のとおりでした。すべてのアルゴリズムは、ユークリッド距離をヒューリスティック関数として使用していました。LRTA* および RTAA* の場合、反復ごとに拡張ノード数を 250 に設定しました。ARA* アルゴリズムは、ヒューリスティックの重みを 2.5 にして実行しました。ランダム性を考慮し、結果の信頼性を確保するために、各アルゴリズムを各グリッドで 100 回実行しました。