Дипломная работа: Сенсоры для навигации мобильного робота

Модель схемы подается в виде набора правильно построенных формул (ППФ) логики производных первого порядка, что отображают собой факты и законы.

Операторная схема определяется наименованием, списком параметров и описаниями в виде ППФ языка логики производных первого порядка: условий применения действий и результат действий. Результат действий, в свою очередь, содержит список вычеркиваний и список добавлений. Операторы порождают разные модели мира путем генерирования новых фактов. Цель системы также подается в виде ППФ тое же самой логики, то есть она является желанной ППФ системы.

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

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

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

Когда таким образом оператор – кандидат найден, условия его применения принимаются как новые подцели системы.

Иерархию целей, подцелей и моделей, порожденную в процессе поиска, можно представить в виде дерева поиска. Каждая вершина такого дерева имеет вид и соответствует заданию достижения модели целевого списка с указанной модели окружения. Пример дерева поиска приведен на рисунке 2.2.

Рисунок 2.2 – Дерево поиска в системе STRIPS

2.3 Реализация систем планирования

Практическая реализация систем планирования включает такие компоненты: модель мира, операторные схемы и цель системы. В частности языком Prolog модель мира, соответствует рис. 2.1 может быть описана набором утверждений:

is_a(room1,room,always)

is_a(room2,room,always)

is_a(room3,room,always)

is_a(door12,door,always)

is_a(door23,door,always)

is_a(box1,object,always)

is_a(box2,object,always)

is_a(box3,object,always)

connects(door12,room1,room2,always)

connects(door23,room2,room3,always)

stands(door12,opened,now)

stands(door23,opened,now)

is_in(box1,room1,now)

is_in(box2,room2,now)

is_in(box3,room3,now)

is_in(robot,room2,now)

is_at(robot,door12,now)

Не тяжело понять содержание базы данных. Она формируется соотношениями: is_a – принадлежность объекта класса, connects – объединение двух объектов третьим, stands – состояние объекта, is_in – местоположение объекта; is_at – общее расположение одного объекта возле другого.