A* - Artificial Intelligence for Robotics Udacity Japanese Russian

A* - Artificial Intelligence for RoboticsYouTube↗ IA↗(long shot)
Education 10.1K views 28 likes 2 dislikes 30 May 2012

Udacity 651K subscribers United States YouTube↗

ではここで講義の主題である A＊について説明しましょう

Теперь я хочу пройти с вами в абсолютное содержание этого класса, которое называется A-Star.

A＊は何年も前にスタンフォード大学のニルス・ニルソンによって考案されました

A-Star был изобретен Нельс Нельсоном в Стэнфорде много лет назад,

A＊は探索アルゴリズムの一種で全ノードを展開するよりも効率的な手法です

и представляет собой вариант алгоритма поиска, что это более эффективно, чем расширяться с каждым узлом.

これまで説明してきたので OPENリストのノードを次々に展開していく

Если вы получили до сих пор, и вы понимаете механизм поиска

探索メカニズムについては理解されていると思います A＊もほぼ似たようなものですがまったく同じというわけではありません

постепенным расширением узлов в открытом списке, A-star почти то же самое но не совсем.

A＊について説明するために先ほどと同じグリッドを使用しましょう

Чтобы проиллюстрировать A-star я буду использовать ту же сетку, как раньше

ただし今回は障害物の構成が異なります

но с другой конфигурацией препятствий.

これはA＊が実にうまく実行される方法の1つです

Это один из способов A-star который выполняется очень хорошо.

下に向かってここまで進むしかありません

Очевидно, что мы вынуждены спуститься сюда,

しかしこの地点ではゴールまでの最適経路を探索しなければいけません

но здесь нам еще предстоит искать оптимальный путь к цели.

プログラムコードで表すとこのようになりゴールまでのすべてのセルを確認できます

Здесь те же проблемы в коде; вы можете увидеть все их здесь.

スタートがここでゴールがここです

Начало набора сюда, цель набора здесь.

実行すると先ほど皆さんが作成したような展開リストになります

Если я запускаю этот код и даю вам расширить список, те, что вы запрограммировали прежде,

ここから下に向かって展開していることが分かりますが

Вы увидите, что расширение идет вниз отсюда,

そのあとは障害物のない空間へと展開しています

но затем он расширяется в открытом пространстве.

この空間で対角線方向に展開し最終的にはゴールの15番目のノードに到達します

Диагонально она расширяется в открытом пространстве и до тех пор пока он, наконец, попадает в цель узла 15.

ゴールに到達するまでに展開が16回実行されています

Это заняло 16 разложений, чтобы добраться до этой точки.

A＊に切り替えて再びコードを実行してみましょう

Позвольте мне теперь включить A-star и запустить код еще раз.

このように0から9までのわずか10回の展開でゴールに到達します

То, что мы сейчас найдем это занимает всего 10 расширений, чтобы добраться до этой точки, от нуля до девяти здесь.

4までは下に展開しますがそれ以降はゴールまで真っすぐに展開します

Таким образом, расширяется до четырех, но затем он расширяется прямо к цели

このエリアには一切踏み込んでいませんこの上部に進むと直進した場合よりも道のりが遠くなることが分かっているようです

никогда не прикасается к этой области здесь, каким-то волшебным образом, что здесь на пути к цели будет больше, чем дальше.

ここに直線経路があるということは指定していません

Теперь я не обманывал. Я не говорил, что есть прямой путь сюда.

次にゴールの隣に障害物を設定して

Итак, позвольте мне положить препятствие прямо здесь, рядом с целью и запустить A-star снова.

A＊を再び実行してみましょうこのように7まで展開しますが

Что вы найдете это расширить до семи здесь

そこからは下から2番目の行へ移動し

но потом переходит на вторую строку здесь,

上の方へ展開してから前回と同様にゴールに到達します

расширяется здесь, а затем попадает в цель еще раз.

ゴールに最大限近づくために必要な最小限の作業量を実行するのがA＊ですさらに詳しく見てみましょう

Таким образом, она как бы делает минимальный объем необходимых работ чтобы сделать максимальный прогресс к цели. Это A-star, и теперь мы смотрим на A-star более подробно.

A＊ではヒューリスティック関数を使用しますセットアップが必要な関数です

A-star использует так называемые эвристические функции, которая является функцией, которая должна быть создана.

値がすべてゼロならすでに実装されている探索アルゴリズムを使用します

Если все нули, то A-star вернется к алгоритму поиска уже реализованного.

ヒューリスティック関数のhを呼び出すと各セルに値を設定する必要があります

Если мы называем эвристическую функцию h, то для каждой ячейки это приводит в стоимость.

値を入れてみましょう

Итак, позвольте мне дать вам несколько значений.

ここの値は1です　障害物が一切ない場合のゴールまでのステップ数です

Вот один: его количество шагов, необходимое для цели, если не было никаких препятствий.

私が書いている1、2、3、4、5などの数値はゴールまでの実際の距離を反映するものではありません

Очевидно, что число я ставлю прямо сейчас, 1, 2, 3, 4, 5, и так далее, не отражают фактического расстояния до цели

障害物が考慮されていないからです

потому что они не считают препятствий.

ヒューリスティック関数は障害物のない世界ではそのままゴールまでの距離を観測します

В мире без препятствий эвристические функции, которые я даю вам будут на самом деле измерять расстояние до цели.

ゴールからどのくらい離れているかは楽観的な推測をするしかありません

Таким образом, эвристическая функция должна оптимистично предположить, как далеко мы от цели.

言い換えるとxy座標で表わされるセルについて楽観的な推測をするということです

Таким образом, для любой клетки х у эвристическая функция должна быть оптимистичным предположением,

つまり推測値は座標xyからゴールまでの実際の距離以下になるということです

что означает меньше или равна длине цели от координат х и у.

場当たりてきなようですが

Сейчас это звучит немного специально,

これで優れたヒューリスティック関数を簡単に適用できるのです

но очень часто вы можете дать хорошие эвристические функции очень легко

エージェントが左、右、上、下に移動できることが分かっていれば

Как и в этом случае здесь. Если мы просто знаем, что агент может двигаться влево, вправо, вверх или вниз,

障害物がない状況でゴールに到達するまでのステップ数を予測するのは非常に簡単で

это очень легко сказать, что есть ряд шагов, которые займет агента

その場合はこの表のようになります

без каких-либо препятствий, чтобы добраться до цели, и что это за таблица здесь.

この表は簡単に自動的に生成されます

Это легко генерируется автоматически.

しかし実際にはこの推測値は低く見積もられます

Сейчас на самом деле это занижены.

例えばこのような障害物があった場合ここからゴールまで9ステップでは足りません

Если препятствия, например, выглядеть так, то отсюда берет вас более чем на 9 шагов чтобы добраться до цели.

山なりに移動して13ステップかかります

Он отнимет у вас 13 шагов к более чем решающему моменту здесь.

ヒューリスティック関数は優れた点があります厳密である必要がないのです

В этом и заключается красота эвристической функции.

厳密であれば計画問題はとっくに解決していたでしょう

Она не должна быть точной. Если бы это была точно что вы уже решали задачи планирования.

数値が同じであった場合は次にどこを探索すべきか知るための関数が必要です

Там должна быть функция, которая поможет вам понять, где искать следующее в случае связей,

その関数はゴールからの距離を実際の距離以下に見積もらないといけません

и это должно быть именно так, что он недооценивает или в лучшем случае равна расстоянию от истинной цели.

Googleの自動運転車では多くの問題においてこのような関数を使用しています

Многие, очень многие проблемы имеют такие функции, как это в наших автомобилях самостоятельного вождения.

実際にここで紹介した関数を使って

Мы используем функцию так же, как это, в самом деле я просто показываю вам функцию,

ソフトウェアでナビゲーションを不要にしています

мы используем в нашем программном обеспечении для свободной формы навигации.

目的地までのユークリッド距離ではなくセルのステップ数が求められます

Она сводится к большому числу которые клетки шаги, но для евклидова расстояния до цели месте.

ヒューリスティック関数がどのようなものであるかお分かりいただけたと思います

Я надеюсь, вы понимаете, как эвристическая функция может выглядеть.

すべてが役立つわけではりませんが多くの有益なヒューリスティック関数が存在し

Она имеет много, много значений эвристической функции, включая установку все к нулю,

すべての値をゼロに設定するものもあります

который не будет действительно помогать мне.

このヒューリスティック関数について考えてみましょう

Так что давайте работать с этой эвристической функции.

コード内でヒューリスティック関数が使用されています

Вот эвристические функции в коде.

手書きの表と同じものです

Вы можете видеть ту же эвристическую функцию.

探索アルゴリズムに関する重要な修正は極めてシンプルなものです

Ключевые модификации теперь для наших алгоритмов поиска очень, очень простые.

ここで再びOPENリストを使用して状態を追加し

У нам вновь есть список, и мы добавим наше положение, запишем г-значение,

g値とともにヒューリスティック値＋g値を記録します

Но мы также запишем г-стоимость плюс эвристическое значение.

ここではg値は0でヒューリスティック値は9です

G-значение здесь ноль; эвристическое значение равно 9.

2つの合計は9でこれをf値と呼びます

Таким образом, сумма двух равно 9, и я называю это F-значение.

f値はg値の累積とヒューリスティック値の合計を表します

Это совокупность г-значение плюс эвристическое значение

ここにある表ではこのようになります

как в таблице здесь.

ノードを展開する場合はg値の最小値ではなく f値の最小値である要素を除外します

Если я сейчас расширю, то я удалю элемент с наименьшим F-значением, а не наименьшее г-значение.

これがA＊の実行です　例をお見せしましょう

Вот и все, что нужно для A-star. Позвольте мне привести вам пример.

OPENリストでここまで進むとします

Скажем, мы пошли в список на всем пути сюда.

ここまですべての状態を展開します

То есть мы расширили все эти положения здесь,

OPENリストにおける現在の位置はここで

и это один присутствующий здесь в списке.

g値は5になります

Наше г-значение будет 5.

ヒューリスティック値は4であり合計は前回と同じく9です

Наша эвристическая функция будет 4, а сумма составляет 9, как раньше.

次にこのノードを展開します

Давайте теперь расширим этот узел.

1つ進んでここに移動するとg値は6に増えます

Мы добираемся до этого здесь, г-значение увеличивается до 6.

g値とヒューリスティック値の合計は 6＋3なので依然として9です

G плюс эвристическая функция все еще будет 9.

さらに展開すると2つの選択肢が登場します

Теперь давайте расширим ее больше, и есть теперь два варианта в конце:

この状態とこの状態です

Это состояние здесь и это состояние здесь.

上に1つ進む場合は［3，2］で右に1つ進む場合は［4，3］になります

Тот, здесь называют 3 2, один по правую называют 4 3.

この場合のg値は両方とも7です

Г-значение здесь, в обоих случаях равна 7,

しかしh値を加えると違いが出ます

Но когда мы добавим h значение мы получаем разницу.

上へ進む場合はh値が4になります

Прям здесь мы находим h-значение в 4.

ゴールから少し離れた位置に移動することになります

Мы отошли немного в сторону от цели в соответствии с эвристической.

合計は11です

Это дает нам всего 11.

一方こちらに進むとh値は2になって7＋2＝9です

В то время как для подачи здесь мы находим h-значение равным 2.

ここで初めてA＊が実質的な違いをもたらしますこのノードよりもこちらのノードの方が展開の優先度が高くなっています

Вот в первый раз, что A-star делает фактические разницы. Он имеет предпочтение, чтобы расширить этот узел здесь над узлом здесь.

g値とh値の合計のf値が一方で9、他方で11である理由を考えてみましょう

Чтобы понять, почему F-значение, сумма g и h, здесь составляет 9, но здесь составляет 11.

ヒューリスティックにおいてこれは何を示しているかというと

Что это отражается в соответствии с эвристическим,

実質的にはこちらの方がこちらに比べて 2ステップ分ゴールに近いということです

этот парень на самом деле на 2 шага ближе к цели, чем этот парень здесь.

このノードはゴールから2ステップの位置にあり

Этот парень, в соответствии с эвристическим, может быть, в 2 шагах от цели,

このノードは少なくとも 4ステップ離れているということになります

и парень здесь не менее 4 шагов.

この場合f値が9対11なので A＊はこのノードを展開します

A-star теперь будет расширять этот узел сюда, потому что его F-значение 9 и 11.

このノードを展開してみると 2つの有効な隣接ノードができます

Так давайте сделаем это. При расширении этого узла мы находим двоих действительных соседей:

この上のノードと右のノードです

Парень здесь и парень справа.

1つ目のノードの座標は［3，3］で 2つ目のノードの座標は［4，4］です

Координаты первого парня являются 3 3. Второй парень 4 4.

これまでと同様にg値は1つずつ増加します

Как и прежде, мы увеличиваем г-значение на единицу.

どちらも8です

Получается восемь в обоих случаях.

次にヒューリスティック値をg値に加えますここにある1つ目の方は3で3＋8＝11です

Теперь мы добавим эвристическую функцию в г-значение, которое для первого здесь составляет 3;

一方右の方のノードのヒューリスティック値は 1となります

В то время как по правую мы получаем один, как эвристической функции.

ノードを展開した結果がこうです

Это результат расширения узла сюда.

これは新しいOPENリストでここでも優先度があります

Вот наш новый список, и опять у нас есть предпочтения.

OPENリストにはこれらの3つの状態があり右側のノードの方が優先度が高くなります

В списке этих трех положений, и мы предпочитаем один по правую

f値が他の2つのf値よりも小さいからです

потому, что его F-значение меньше, чем в двух других F-значениях.

このf値は9ですがこちらのf値は11です

Здесь 9; вот здесь F-значение равно 11.

ここで再び展開するとゴール状態になります

Таким образом, мы снова расширяемся и в расширении станет задачей,

ゴール状態が検出され迷路のこの上の部分は展開されずに終わります

и тогда мы находим поставленную цель, и мы сделали без постоянного расширения в лабиринте здесь.

まるで魔法のようですが重要なのは追加情報を与えるということです

Чувствуется, как по волшебству, но главное здесь заключается в предоставлении дополнительной информации,

ヒューリスティック関数と呼ばれる追加情報を使用して探索を誘導します

так называемые эвристические функции, мы можем вести поиск.

行き詰まったときはゴール状態に近く見えるノードを選択することができるので

Когда у нас есть тупик, мы можем выбрать узел, который выглядит ближе к цели государства.

結果としてゴールに近づく可能性が高くなります

В результате мы, вероятно, добились большего прогресса в достижении цели.