Выявление значимого контекста

Учитывая вышесказанное, можно сделать заключение, что выявление значимого контекста является важной составляющей планировщика, особенно если необходимо выполнять планирование в больших предметных областях. В [Трофимов, 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]. К сожалению, домен с транспортировками не позволяет продемонстрировать эту особенность.