Влияние нерелевантного контекста на скорость и качество работы планировщиков. Описание нескольких методов, которые можно использовать для выявления значимого контекста. Приведение некоторых экспериментальных результатов, связанных с этой проблемой.
Аннотация к работе
Современные универсальные планировщики не учитывают тот факт, что многие объекты, присутствующие в формальном описании предметной области, не имеют отношения к решаемой в настоящий момент задаче. Можно повысить эффективность систем планирования, если исключить из рассмотрения эти «нерелевантные» объекты. В этой статье подробно рассматривается влияние нерелевантного контекста на скорость и качество работы планировщиков, описывается несколько методов, которые можно использовать для выявления значимого контекста, а также приведены некоторые экспериментальные результаты, связанные с этой проблемой. Значимый контекст составляют объекты, фигурирующие в цели, а также все объекты, находящиеся “непосредственно под” этими объектами и “непосредственно или опосредованно над” этими объектами. Так как использовался планировщик с систематичной формой выбора, для возможности получения новых решений (даже в случае точного совпадения целевого и начального городов в новой задаче и прецеденте) использовались случайные перестановки элементов в списке городов, составляющих значимый контекст.Выявление значимого контекста рассуждений вносит существенный вклад в производительность систем планирования и может повышать качество решений за счет снижения вероятности появления неадекватных планов.
Введение
нерелевантный контекст скорость планировщик
Эффективное планирование является одной из ключевых составляющих успешного функционирования и развития промышленности и бизнеса. Однако задача планирования является трудной для человека в силу того, что зачастую требуется учитывать огромное количество факторов, влияющих на осуществимость плана и его эффективность. В связи с этим ведется интенсивный поиск средств и методов, которые позволили бы решать эту задачу при помощи вычислительной техники.
В описании предметной области, для которой решается задача планирования, часто фигурирует довольно большое количество объектов. Это обусловлено тем, что в рамках одной предметной области решается множество различных задач планирования, связанных с различными объектами. Современные универсальные планировщики не учитывают тот факт, что многие объекты, присутствующие в формальном описании предметной области, не имеют отношения к решаемой в настоящий момент задаче. Можно повысить эффективность систем планирования, если исключить из рассмотрения эти «нерелевантные» объекты.
Проблема нерелевантного (по отношению к задаче планирования) контекста была сформулирована в [Трофимов, 2005]. В этой статье подробно рассматривается влияние нерелевантного контекста на скорость и качество работы планировщиков, описывается несколько методов, которые можно использовать для выявления значимого контекста, а также приведены некоторые экспериментальные результаты, связанные с этой проблемой.
Влияние незначимого контекста на скорость работы планировщика
Влияние нерелевантного контекста обусловлено потенциальной возможностью использования объектов. Основная функция планировщика - строить гипотезы относительно того, каким способом может быть достигнута цель (или каким ограничениям должен удовлетворять план), а затем проверять состоятельность этих гипотез. Проверка гипотезы заключается в том, чтобы удостовериться в невозможности построить план, если гипотеза не верна. Таким образом, для опровержения гипотезы, необходимо попытаться найти план всеми возможным способами, предполагая, что гипотеза верна.
Такой подход приводит к тому, что планировщик, при рассмотрении очередной цели, обязан принимать во внимание все способы ее достижения - все допустимые виды действий, а также все инструментальные, локативные, темпоральные и прочие характеристики действия. В больших предметных областях это влечет необходимость перебора огромного числа вариантов, что негативно сказывается на скорости работы системы планирования.
Хорошей демонстрацией данной проблемы является известный домен с кубиками, содержащий четыре действия (pickup, putdown, stack и unstack). Рассмотрим задачу, изображенную на рисунке 1.
Рисунок 1 Нерелевантный контекст в мире кубиков
Несмотря на то, что в оптимальное решение задачи вовлечено только три кубика (A, B и C), присутствие в домене других кубиков, лежащих на столе, влияет на время, необходимое для получения решения. Будем называть это явление эффектом пассивного соседства.
Чтобы установить, сколь велико может быть влияние эффекта пассивного соседства в домене с кубиками, был поставлен следующий эксперимент. Для проведения эксперимента автором была реализована означенная версия алгоритма планирования SNLP [MCALLESTER et al., 1991] с перечисленными ниже модификациями.
Все недетерминированные выборы заменены на систематичные.
Предусловие может считаться угрозой (по аналогии с планировщиком REPOP [Nguyen et al., 2001]).
Использованы дизъюнктивные условия безопасности (по аналогии с планировщиком REPOP [Nguyen et al., 2001]).
При добавлении в план всякого шага Step сразу добавляются ограничения (start < Step) и (Step < finish).
Барьер глубины поиска был установлен равным 20.
В ходе эксперимента измерялось время работы планировщика над решением задачи с двумя нерелевантными кубиками, изображенной на рисунке 1. Измерялось также время работы над решением этой же задачи, но с большим числом нерелевантных кубиков, лежащих на столе. Результаты приведены в таблице 1.
Таблица 1 Влияние нерелевантного контекста в мире кубиков
Количество нерелевантных кубиков 2 3 4 5 10
Рассмотрено узлов пространства поиска, тыс. 43 104 228 459 6576
Время поиска, сек. 1,7 2,7 4,9 8,2 70
Из таблицы видно, что в этом домене влияние нерелевантного контекста велико. В общем случае, степень влияния зависит от самого домена и устройства планировщика.
Влияние незначимого контекста на качество планов
Нерелевантный контекст оказывает влияние не только на скорость планирования, но и на адекватность получаемых планов.
Решения, которые мы хотим получать от планировщиков, должны быть адекватны миру, в котором мы живем. С практической точки зрения, нас не интересуют все возможные способы решения проблемы. Достаточно найти одно или несколько приемлемых, несмотря на возможность существования множества других решений. Когда нам требуется повесить картину, вряд ли мы пойдем за молотком к соседу, если у нас имеется свой собственный молоток (несмотря на то, что любой из этих путей позволяет достичь цель). К тому же, как правило, адекватные решения являются наиболее короткими, так как людям свойственно находить наиболее простые пути решения проблем, а, следовательно, и поиск их будет осуществляться быстрее.
Так как для прикладных систем вопрос адекватности плана является ключевым, эта проблема всегда рассматривалась исследователями проблемы планирования как одна из важнейших. Возможным способом решения этой проблемы может быть разработка эвристик, опирающихся на знания о предметной области. Но в этом случае нужно выполнять кропотливую работу над эвристическими алгоритмами, причем для каждого вида задач планирования, которые предполагается решать. Можно также применить рассуждения по прецедентам для повышения адекватности. Например, такой подход был использован в системе PRODIGY[Veloso et al., 1993]. Но в этой системе отбор релевантных объектов не рассматривался как ключевой; больше внимания уделялось выбору адекватных действий. Релевантные объекты жестко связывались со структурной составляющей прецедента, что ограничивало возможность получения новых решений с теми же объектами.
Выявление значимого контекста могло бы сыграть существенную роль в увеличении вероятности нахождения адекватного плана. Если убрать из рассмотрения все нерелевантные инструменты, локативы и другие характеристики действия, то мы не оставим возможности для появления неадекватных планов с их участием.
Выявление значимого контекста
Учитывая вышесказанное, можно сделать заключение, что выявление значимого контекста является важной составляющей планировщика, особенно если необходимо выполнять планирование в больших предметных областях. В [Трофимов, 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 Выявление значимого контекста в задаче с транспортировками методом рассуждений по прецедентам.
Задача A B C D E рассмотрено узлов 10496 261 270 592 1071 время поиска, мс. 2438 94 47 141 266
Во всех случаях, когда использовалась прецедентная информация, наблюдается значительное увеличение скорости работы планировщика.
Еще одним интересным эффектом применения в данном домене рассуждений по прецедентам вместе со случайным микшированием является то, что планировщик может со временем найти точный значимый контекст, если изначально было найдено его надмножество. В таблице 3 показан процесс формирования точного значимого контекста. Решаемая задача вновь требовала трех перемещений (в оптимальном варианте). Планировщик запускался с одной и той же задачей три раза; при первом запуске библиотека прецедентов была пуста.
Таблица 3 Процесс уточнения контекста в задаче с транспортировками.
№ запуска 1 2 3 рассмотрено узлов > 58 тыс. 355 297 время поиска 15 с 94 мс 79 мс объектов в значимом контексте 29 6 5
Из таблицы видно, что уточнение (уменьшение) значимого контекста приводит к увеличению скорости работы планировщика.
Случайное микширование или использование планировщика с недетерминированными выборами позволяет получать решения, отличающиеся по структуре от прецедентных решений, что невозможно, например, в PRODIGY[Veloso et al., 1993]. К сожалению, домен с транспортировками не позволяет продемонстрировать эту особенность.
Выявление значимого контекста методом рассуждений по прецедентам: открытые вопросы
В методологии рассуждений по прецедентам, когда ставится новая задача, требуется найти соответствующий ей прецедент. Поиск прецедента предполагает наличие свойств (признаков), которые используются при сопоставлении новой задачи и прецедента, и в зависимости от степени сходства этого множества признаков принимается решение об использовании прецедента. В домене с транспортировками в качестве таких признаков мы использовали пункты назначения и отбытия. Однако в целом вопрос о выборе подходящих свойств, а также процедуры сопоставления и выбора решения, весьма сложен.
Обычно в планировании на основе прецедентов (case-based planning) в качестве сопоставляемых признаков используется только постановка задачи планирования, то есть начальное состояние и цель. Причем эти признаки рассматриваются как множества: множество литералов в описании начального состояния и множество подцелей. В действительности во многих доменах нельзя говорить о сходстве задач без учета структурной составляющей - должны приниматься во внимание связи между объектами в начальном состоянии и цели. Однако рассмотрение задач планирования в виде графов осложнено тем, что трудно определять степень сходства графов. Вообще, даже если задачу планирования рассматривать как пару множеств (множество фактов о начальном состоянии и множество подцелей), для многих доменов трудно придумать неэвристическую метрику подобия для реализации сопоставления. Объекты должны обладать довольно большим набором свойств, причем явно представленных в описании домена, чтобы можно было использовать какие-либо независимые от домена метрики подобия.
Еще один вопрос, связанный с проблемой выявления значимого контекста методом рассуждений по прецедентам, состоит в том, чтобы установить, объекты какого рода должны попадать в значимый контекст? В домене с транспортировками значимый контекст составлялся из всех объектов, попавших в решение. Однако в общем случае может потребоваться более гибкий подход. Следует отметить, что контекст может состоять только из объектов, присутствие которых гарантировано во всех возможных задачах планирования, и свойства которых сохраняются от задачи к задаче. На этот вопрос следует обратить внимание в силу того, что в PDDL объекты, их свойства и отношения между ними являются элементами задачи, а не предметной области. То есть набор конкретных экземпляров объектов (их свойства и отношения между ними) может меняться от задачи к задаче. Если мы допустим включение таких объектов в значимый контекст, то прецеденты окажутся бесполезны.
В PDDL есть возможность декларировать объекты, характерные для домена в целом (constants), а не для конкретной задачи. Однако PDDL не допускает описание свойств этих объектов и отношений между ними в файле домена. Это можно было бы сделать при помощи аксиом с пустой посылкой, но пустая посылка в PDDL недопустима. Поэтому для описания свойств и отношений для константных объектов требуется расширение языка. Если описать объекты, характерные для предметной области в целом, таким образом, то значимый контекст можно составлять из объектов, описанных как PDDL-константы. А при решении задач использовать значимый контекст, объединенный с множеством всех объектов описанных в файле задачи.
Таким образом, применение рассуждений по прецедентам (CBR) для выявления значимого контекста без использования эвристических процедур ограничено лишь узким кругом доменов. Эффективному использованию CBR препятствуют сложности, связанные с выбором объектов, которые должны быть включены в значимый контекст, а также сложности, связанные с поиском прецедента.
Перспективные направления исследований
Во-первых, следует отметить, что возможности применения рассуждений по прецедентам для выявления значимого контекста не ограничиваются описанными выше методами. Кажется возможным, выявлять значимый контекст не только из числа константных PDDL-объектов, но и из объектов, перечисленных в файле задачи. При этом нужно включать в контекст не конкретные объекты, а их типы и свойства, то есть набор признаков для фильтрации исходного множества объектов.
Во-вторых, к задаче выявления значимого контекста можно подойти как к задаче классификации или распознавания. На вход классификатора подается задача планирования и проверяемый на принадлежность значимому контексту объект. На выходе два класса: класс принадлежащих и класс не принадлежащих значимому контексту объектов. Обучив классификатор на множестве типовых решений, можно в дальнейшем для каждой новой задачи и каждого объекта сказать, принадлежит ли объект значимому контексту или нет. Остается открытым вопрос, как представить задачу планирования в виде вектора признаков и нужно ли это делать?
В-третьих, интересно было бы попробовать отбирать объекты в контекст по ассоциативному принципу. Например, можно построить сеть ассоциаций между объектами следующим образом. Изначально связываются все объекты и силы связей одинаковы. Если объекты принимают участие в решении задачи в рамках одного действия, то связь между этими объектами усиливается. Таким образом, между объектами, которые часто используются вместе, будут устанавливаться более сильные связи. Решая новую задачу, мы можем в качестве значимого контекста брать объекты, непосредственно фигурирующие в постановке задачи, а также сильно связанные с ними объекты.
В-четвертых, можно попробовать подойти к задаче с другой стороны - выявлять нерелевантные объекты. В каких-то предметных областях именно такой подход может оказаться эффективным. Кроме того, это решает проблему, связанную с выбором объектов, которые должны войти в значимый контекст. Для нерелевантного контекста присутствие или отсутствие объекта в постановке задачи не играет роли, так как нерелевантный контекст работает по принципу фильтра.
Вывод
Выявление значимого контекста рассуждений вносит существенный вклад в производительность систем планирования и может повышать качество решений за счет снижения вероятности появления неадекватных планов. Для многих предметных областей можно построить эффективные эвристические процедуры, которые позволят выявлять значимый контекст, опираясь на постановку задачи планирования. Но, вероятно, лишь в немногих доменах можно использовать для решения этой задачи рассуждения по прецедентам без эвристик. Однако способы выявления значимого контекста не ограничиваются исследованными методами. Остаются непроверенными ассоциативные методы и подход к задаче с позиций классификации.
Список литературы
[MCALLESTER et al., 1991] MCALLESTER D.A., Rosenblitt D., Systematic Nonlinear Planning. // Proc. of the 9th National Conference on Artificial Intelligence (AAAI-91), - Anaheim: AAAI Press/MIT Press, 1991.
[Nguyen et al., 2001] XUANLONG Nguyen, Subbarao Kambhampati, Reviving Partial Order Planning. // Proc. of the 17th IJCAI, - Seattle: Morgan Kaufmann, 2001.
[Veloso et al., 1993] Veloso M.M., Carbonell J.G., Towards Scaling Up Machine Learning: A Case Study with Derivational Analogy in PRODIGY. In Machine Learning Methods for Planning, - USA:Morgan Kaufmann, 1993.
[Трофимов, 2005] Трофимов И.В. Значимый контекст рассуждений в задаче планирования. //Труды Первой международной конференции "Системный анализ и информационные технологии" САИТ-2005: В 2-х томах. - М.:КОМКНИГА, 2005.