Иерархическая целевая сеть (HTN) в AI

Question

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

Например:

«Сесть на автобус» - это HLA, т. Е.пойти в автобус "," купить билет "," сесть "и т. д.

Я не прав?Был бы признателен за простое объяснение.

Answer 1

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

В общих чертах HTN решает проблемуиспользуя очень человеческий подход к планированию, в котором основное внимание уделяется абстракции и альтернативам.

Альтернативы: Давайте рассмотрим пример путешествия от знаменитого SHOP HTN Planner (http://www.cs.umd.edu/projects/shop/description.html). Представьте, что вы спросили меня, как добраться из центра города доПарк. Я мог бы сказать: «Ну, это 2 км, но, если это хорошо, я бы просто прогуляться. Однако, если идет дождь, и у вас есть такси, я бы взять такси. В противном случае,если у вас есть проезд на автобусе, просто сядьте на автобус ». Абстрактная вещь, которую вы выполняете, например« путешествие из одного места в другое », известна в HTN как« Задача ». Три альтернативы, которые я дал для выполнения, известны как« Методы »в HTN. Обратите внимание, что у каждого метода есть «условие», которое сопровождает его: ходите, если это хорошо, возьмите такси, если у вас есть тариф, и т. д.

Абстракция: нете, что эти 3 метода находятся на довольно высоком уровне абстракции.Вы также можете спросить меня, как выполнить метод «TakeABus».Я бы сказал что-то вроде: «Ну, подожди автобус № 1 на остановке« Центр города », заплати водителю 1 доллар и довези его до остановки« Парк »». Эти три задачи известны в HTN как «Подзадачи»»Метода« TakeABus ».В HTN методы делают то, что делают, разбивая их на подзадачи.Теперь, это довольно полный ответ для человека, но, возможно, нет, если бы мы разговаривали с роботом.В этом случае нам может понадобиться еще раз разложить задачу «PayTheDriver $ 1» на что-то вроде «Дотянись до своего кармана, возьми купюру в 1 доллар, передай водителю».Каждый из них может быть разложен до тех пор, пока мы наконец не найдем что-то, что робот сможет сделать.Последний шаг HTN, часть, которая фактически выполняется, называется «оператор».Степень детализации, которую необходимо получить до того, как вы закончите (и у вас есть Оператор), зависит от типа системы, которую вы строите.Большая часть разработки модели HTN заставляет задуматься о правильных абстракциях.

Итак, HTN состоят из следующих частей:

• Состояние мира: выв центре города.Стоимость такси составляет 2 доллара.Стоимость проезда на автобусе составляет 1 доллар.Расстояние от центра города до парка 2км.Задачи: Что можно сделать абстрактно в мире (может быть несколько способов сделать это!): Путешествие от А до Б. Прогулка от А до Б. Заплатите Водителю X $.Дождитесь автобуса A на остановке B.

• Операторы: Как выполнять абстрактные задачи, когда их можно «просто выполнить» без дальнейшего объяснения.Они фактически изменяют состояние мира.Если вы человек, это могут быть операторы: заплатите водителю $ 1, поездка на автобусе № 1 до остановки «Park».Если вы робот, это может быть: Переместите шаговый двигатель вперед на 100 шагов, включите прожектор

• Методы: как выполнять абстрактные задачи, когда они включают несколько шагов или более подробные планы.У них есть условие, когда их можно использовать, и набор подзадач для их выполнения: МЕТОД: «Путешествие от А до Б». СОСТОЯНИЕ: погода плохая, и у вас есть проезд на автобусе, ПОДЗАДАЧИ: Ждите автобуса уостановка автобуса, платите водителю и езжайте на нем до остановки

Сам алгоритм довольно прост.Вы начинаете со списка задач или целей, таких как «Перейти из центра города в парк» и с пустого списка планов:

• Удалите и начните с первой цели в списке целей
• Проверьте, есть лиэто оператор, который знает, как это сделать.Если это так, добавьте оператор в конец списка планов (поскольку операторы могут «просто быть выполнены») и продолжайте с # 1
• Проверьте, есть ли методы, которые знают, как это сделать.Если это так, добавьте их подзадачи в начало нашего списка целей и перейдите к # 1. Если есть несколько методов, продублируйте текущее состояние мира и запустите алгоритм с каждым независимо.Каждое успешно выполненное решение будет отличаться
• Повторять до тех пор, пока список целей не станет пустым
• Когда все выполнено, в списке планов у вас есть решение

У меня есть серия блогов, которые довольно подробно рассказывают об этом, включая исходный код и другие примеры, если вам нужно больше подробностей: https://blog.inductorsoftware.com/blog/htnoverview

Answer 2

Во-первых, иерархическая сеть задач - это синтаксический анализатор для данного плана.В этом примере план:

1 takebus
  1.1 gotobus
  1.2 buyticket
  1.3 sitdown

можно протестировать на HTN-сети, и он ответит на запрос: «План действителен» и «Выполнение заняло 30 минут».Другой план, который немного изменен, также может быть выполнен для HTN-сети.

То, что делает сообщество планирования вокруг конференции ICAPS, выясняет, как строить иерархические сети задач.Они часто используют Prolog-диалект, PDDL, для создания сложных деревьев поведения.Например, для разбора планов по проблеме робота докеров или для разбора планов из домена мира блоков.

Во-вторых, термин иерархическое планирование сети задач также используется, если цель состоит в том, чтобы найти оптимальный план дляданный домен.Здесь у нас уже есть описание PDDL, и мы заинтересованы в поиске кратчайшего плана.Это полезно в контрольных задачах, в основном с целью автономного игрового процесса.

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