Целенаправленный решатель, страница 7

Таким образом, попытка построить дедуктивный решатель, используя в полной степени формализм принципа резолюций, оказалась, как показала система QA3, также неуспешной. При разработке последующих версий решателей представлялось бы целесообразным отказаться от такого полного формализма, на­пример, отказаться от поиска подходящих операторов на основе дедуктивного вывода и вернуться к их процедурному поиску, как это было сделано в системе GPS. Это позволило бы в ходе пост­роения плана действий использовать для выбора операторов эффективную стратегию GPS, а для оценки достижимости целей и применимости операторов — метод резолюций.

Так возникла планирующая система STRIPS (Stanford Research Institute Problem Solver), использующая декларативно-процедуральное представление знаний в сочетании с эвристиче­ским поиском [Файкс, Нильсоы, 1971; Файкс, Харт, Пильсон, 1972а, б]. Эта особенность в сочетании с использованием макрооператоров, формируемых на основе обучения решателя STRIPS, позволила повысить его эффективность по сравнению с си­стемой QA3.

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

Для пояснения возьмем, к примеру, действие «перемещение робота /?». Его основной эффект — изменение местоположения робота — априори известно и поэтому может быть введено в опи­сание действия в виде списков вычеркивания и добавления. Те­перь допустим, что в планирующую систему STRIPS, в памяти которой содержится описание указанного действия, введено опи­сание исходной ситуации, в частности местоположение с некото­рого предмета а. И пусть в ходе решения задачи выработанный роботом план действий требует такого перемещения, при котором он оказывается в окрестности места с. Сразу появляется зараее непредусмотренный эффект действия — факт РЯДОМ (й, а), ие введенный заранее в знания планировщика при описании резуль­тата действия перемещения, по который тем не менее может оказаться существенным для дальнейшего поведения робота. Не­трудно догадаться, что подсистема логического вывода в подобно]! системе быстро накапливает противоречивые факты и сама ста­новится противоречивой. Не решало проблемы и предложение Хайеса [1971] аксиоматизировать причинно-следственные связи предметного мира и снять таким образом негативный аспект проблемы побочных эффектов, т. е. автоматически выводить все то, что не меняется в результате применения действия.

В итоге STRIPS оказался работоспособным лишь для решения задач в весьма простых проблемных средах типа мира игру­шечных кубиков.

Авторы решателей задач, таких, например, как STRIPS или GPS, предполагали получить удовлетворительное решение проб­лемы поиска глобальных целей, основываясь лишь на использо­вании эффективных поисковых эвристик. Однако это не решило проблемы — пространство поиска оставалось чрезмерно большим.

Использование в системе STRIPS обобщенных планов, не­сомненно, представляло определенный шаг вперед в решении про­блемы эффективного поиска, но, к сожалению, лишь только шаг. Главный недостаток процедуры обобщения планов (формиро­вания макрооператоров) в системе STRIPS заключался в том, что опа не включала в себя процедуру обобщения моделей мира. Вследствие этого макрооператор, представляя семантически свя­занную последовательность элементарных операторов, сохранял каждую деталь условий применения и списков добавлений этих операторов. Метод обобщения планов приводил к настолько большим конъюнкциям условий применения и настолько большим спискам добавлений, что эффективность решения практически сложных задач оказалась при этом невысокой.