Значимый контекст рассуждений в задаче планирования: эксперименты и перспективы

Учитывая вышесказанное, можно сделать заключение, что выявление значимого контекста является важной составляющей планировщика, особенно если необходимо выполнять планирование в больших предметных областях. В [Трофимов, 2005] упоминалось, что пути решения этой подзадачи, видимо, нужно искать в области эвристик и рассуждений по прецедентам.

Эвристики действительно могут быть эффективны для решения данной проблемы. Например, для домена с кубиками эвристика, выявляющая значимый контекст точно, достаточно проста. Ее суть раскрывается в следующей фразе. Значимый контекст составляют объекты, фигурирующие в цели, а также все объекты, находящиеся “непосредственно под” этими объектами и “непосредственно или опосредованно над” этими объектами. Экспериментально установлено, что эффект этой эвристики таков, как если бы мы в таблице 1 заменили все значения во второй строке на 5, а в третьей строке -- на 0,4.

Что касается рассуждений по прецедентам, то в целях демонстрации того, что этот метод также может эффективно использоваться для выявления значимого контекста, был поставлен следующий эксперимент. Решалась задача транспортировки из города в город. Чтобы совершить перемещение из города в город, должна существовать транспортная магистраль между этими городами (магистрали однонаправленные). Для простоты домен содержал единственное действие.

(:action move

:parameters (?from - location ?to - location)

:precondition ( and (at ?from) (route ?from ?to) )

:effect (and (not (at ?from)) (at ?to))

)

От задачи к задаче множество городов, а также карта магистралей, не изменялись. В модели предметной области были описаны 29 городов и 106 магистралей.

В качестве системы планирования использовался описанный выше планировщик. Прецедентом служила следующая информация:

начальное местоположение перемещаемого объекта,

целевое местоположение перемещаемого объекта,

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

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

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

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

близость исходного города в новой задаче к исходному городу в прецеденте,

количество городов в значимом контексте (чем меньше, тем лучше).

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

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

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

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

В ходе эксперимента были получены следующие результаты. В таблице 2 отражено, как влияет использование значимого контекста из прецедента на производительность планировщика. Исходная задача требовала для получения (оптимального) решения трех перемещений (move). Буквами в таблице обозначены решавшиеся задачи:

A -- решение исходной задачи -- формирование прецедента;

B -- повторное решение задачи с использованием полученного прецедента;

C -- решение задачи с целевым городом, находящимся вблизи от целевого города прецедента;

D -- решение задачи с исходным городом, находящимся вблизи от исходного города прецедента;

E -- решение задачи, сочетающей условия из задач C и D.

Таблица 2 Выявление значимого контекста в задаче с транспортировками методом рассуждений по прецедентам.

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

Еще одним интересным эффектом применения в данном домене рассуждений по прецедентам вместе со случайным микшированием является то, что планировщик может со временем найти точный значимый контекст, если изначально было найдено его надмножество. В таблице 3 показан процесс формирования точного значимого контекста. Решаемая задача вновь требовала трех перемещений (в оптимальном варианте). Планировщик запускался с одной и той же задачей три раза; при первом запуске библиотека прецедентов была пуста.

Таблица 3 Процесс уточнения контекста в задаче с транспортировками.

Из таблицы видно, что уточнение (уменьшение) значимого контекста приводит к увеличению скорости работы планировщика.

Случайное микширование или использование планировщика с недетерминированными выборами позволяет получать решения, отличающиеся по структуре от прецедентных решений, что невозможно, например, в PRODIGY[Veloso et al., 1993]. К сожалению, домен с транспортировками не позволяет продемонстрировать эту особенность.

Выявление значимого контекста методом рассуждений по прецедентам: открытые вопросы

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

Обычно в планировании на основе прецедентов (case-based planning) в качестве сопоставляемых признаков используется только постановка задачи планирования, то есть начальное состояние и цель. Причем эти признаки рассматриваются как множества: множество литералов в описании начального состояния и множество подцелей. В действительности во многих доменах нельзя говорить о сходстве задач без учета структурной составляющей -- должны приниматься во внимание связи между объектами в начальном состоянии и цели. Однако рассмотрение задач планирования в виде графов осложнено тем, что трудно определять степень сходства графов. Вообще, даже если задачу планирования рассматривать как пару множеств (множество фактов о начальном состоянии и множество подцелей), для многих доменов трудно придумать неэвристическую метрику подобия для реализации сопоставления. Объекты должны обладать довольно большим набором свойств, причем явно представленных в описании домена, чтобы можно было использовать какие-либо независимые от домена метрики подобия.

Еще один вопрос, связанный с проблемой выявления значимого контекста методом рассуждений по прецедентам, состоит в том, чтобы установить, объекты какого рода должны попадать в значимый контекст? В домене с транспортировками значимый контекст составлялся из всех объектов, попавших в решение. Однако в общем случае может потребоваться более гибкий подход. Следует отметить, что контекст может состоять только из объектов, присутствие которых гарантировано во всех возможных задачах планирования, и свойства которых сохраняются от задачи к задаче. На этот вопрос следует обратить внимание в силу того, что в PDDL объекты, их свойства и отношения между ними являются элементами задачи, а не предметной области. То есть набор конкретных экземпляров объектов (их свойства и отношения между ними) может меняться от задачи к задаче. Если мы допустим включение таких объектов в значимый контекст, то прецеденты окажутся бесполезны.

В PDDL есть возможность декларировать объекты, характерные для домена в целом (constants), а не для конкретной задачи. Однако PDDL не допускает описание свойств этих объектов и отношений между ними в файле домена. Это можно было бы сделать при помощи аксиом с пустой посылкой, но пустая посылка в PDDL недопустима. Поэтому для описания свойств и отношений для константных объектов требуется расширение языка. Если описать объекты, характерные для предметной области в целом, таким образом, то значимый контекст можно составлять из объектов, описанных как PDDL-константы. А при решении задач использовать значимый контекст, объединенный с множеством всех объектов описанных в файле задачи.

Таким образом, применение рассуждений по прецедентам (CBR) для выявления значимого контекста без использования эвристических процедур ограничено лишь узким кругом доменов. Эффективному использованию CBR препятствуют сложности, связанные с выбором объектов, которые должны быть включены в значимый контекст, а также сложности, связанные с поиском прецедента.

Перспективные направления исследований

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

Во-вторых, к задаче выявления значимого контекста можно подойти как к задаче классификации или распознавания. На вход классификатора подается задача планирования и проверяемый на принадлежность значимому контексту объект. На выходе два класса: класс принадлежащих и класс не принадлежащих значимому контексту объектов. Обучив классификатор на множестве типовых решений, можно в дальнейшем для каждой новой задачи и каждого объекта сказать, принадлежит ли объект значимому контексту или нет. Остается открытым вопрос, как представить задачу планирования в виде вектора признаков и нужно ли это делать?

В-третьих, интересно было бы попробовать отбирать объекты в контекст по ассоциативному принципу. Например, можно построить сеть ассоциаций между объектами следующим образом. Изначально связываются все объекты и силы связей одинаковы. Если объекты принимают участие в решении задачи в рамках одного действия, то связь между этими объектами усиливается. Таким образом, между объектами, которые часто используются вместе, будут устанавливаться более сильные связи. Решая новую задачу, мы можем в качестве значимого контекста брать объекты, непосредственно фигурирующие в постановке задачи, а также сильно связанные с ними объекты.

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

Заключение

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

Список литературы

[Трофимов, 2005] Трофимов И.В. Значимый контекст рассуждений в задаче планирования. //Труды Первой международной конференции "Системный анализ и информационные технологии" САИТ-2005: В 2-х томах. -- М.:КомКнига, 2005.