Искусственный интеллект

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

Для описания доменов, задач было взято подмножество языка PDDL. В созданной системе поддерживаются только необходимые для неё языковые средства PDDL (Planning Domain Definition Language):
• описание типов;
• описание предикатов;
• описание действий;
• описание множества рассматриваемых объектов;
• описание начального состояния;
• описание целевого состояния.

Далее идёт РБНФ (Расширенная форма Бэкуса — Наура) входного языка планировщика.

РБНФ для описания доменов:
<domain> ::= (define (domain <name> ) (:requirements :strips :typing) <types-def> <predicates-def> <actions-def> )
<types-def>::= (:types <type>+ )
<type>::=<name>
<variable>::= ?<name>
<predicates-def>::= (:predicates <atomic-formula-with-or-without-types>+ )
<atomic-formula-with-or-without-types>::= ( <predicate> <list-varibles-with-or-without -type>* )
<predicate>::=<name>
<list-varibles-with-or-without -type>::= <variable>+ - <type> | <variable>+
<actions-def>::=<action>+
<action>::= (:action <name> :parameters ( <list-varibles-with-type> ) :precondition (and <atomic-formula>+ ) :effect (and <atomic-formula>+ ))
<atomic-formula>::= (not ( <predicate> <variable>* )) | ( <predicate> <variable>* )
РБНФ для описания задач:
<task>::= (define (problem <name> ) (:domain <name> ) <list-objects> <list-init> <list-goal> )
<list-objects>::= (:objects <objects-types>+ )
<objects-types>::=<object>+ - <type>| (either <type>+ )
<object>::=<name>
<list-init>::= (:init <list-predicates-initialization >+ )
<list-predicates-initialization>::= ( <predicate> <object>* )
<list-goal>::= (:goal (and <list-predicates-initialization >+ ))

 

Пример: вездеход (робот) должен отправить данные о ресурсах – нефти, грунте, воде, которые расположены в точках А, Б, В соответственно. Для этого есть действия – движение из одной точки в другую, сбор ресурса, передача информации о ресурсе. Для того, что бы собрать ресурс, вездеход должен находиться в той же точке, где находится ресурс. Для передачи данных о ресурсе, вездеход должен собрать данный ресурс. Начальное состояние системы – вездеход находится в точке А, также в точке А находится нефть, в точке Б – грунт, в точке В – вода.

Описание на входном языке:

Домен:

(define (domain rovers_classical)
(:requirements :strips :typing)
(:types location data)
(:predicates
(at ?x - location)
(avail ?d - data ?x - location)
(comm ?d - data)
(have ?d - data))
(:action drive
:parameters (?x ?y - location)
:precondition (and(at ?x))
:effect (and (at ?y) (not(at ?x))))
(:action commun
:parameters (?d - data)
:precondition (and(have ?d))
:effect (and(comm ?d)))
(:action sample
:parameters (?d - data ?x - location)
:precondition (and (at ?x) (avail ?d ?x))
:effect (and(have ?d)))
)

Задача:

(define (problem rovers_classical1)
(:domain rovers_classical)
(:objects
soil water rock - data
alpha beta gamma - location)
(:init (at alpha)
(avail soil alpha)
(avail rock beta)
(avail water gamma)
)
(:goal (and
(comm soil)
(comm water)
(comm rock)
(at alpha)))
)

Домен во входном языке системы будет представлять собой набор типов, предикатов над переменными этих типов, действий. Любой тип домена описывается конструкцией:
<types-def>::= (:types <type>+ )
<type>::= <name>
Например: (:types location data). Описаны 2 типа домена: location и data.
Каждый предикат домена описывается конструкцией:
<predicates-def>::= (:predicates <atomic-formula-with-or-without-types>+ ) 
<atomic-formula-with-or-without-types>::= ( <predicate> <list-varibles-with-or-without -type>* )
<predicate>::=<name>
<list-varibles-with-or-without -type>::= <variable>+ - <type> | <variable>+
<type>::=<name>
<variable>::= ?<name>
Например:
(:predicates
(at ?x - location)
(avail ?d - data ?x - location))
Описаны предикаты at, avail. При этом, в определении данных предикатов фигурируют параметры определённых ранее типов location и data. В данной задаче предикат (at ?x) предполагает нахождение робота в точке ?x. (avail ?d ?x) – ресурс ?d находится в точке ?x. При определении предикатов используются параметры. Если их инициализировать объектами из задачи, то получаем факты (утверждения). Возможен вариант объявления предиката, у которого будут не обозначены типы переменных. В этом случае, подразумевается то, что переменная принадлежит любому типу.
Для действий определяются набор переменных, предусловие и эффект. Последние два состоят из формул над определёнными ранее предикатами над переменными данного действия. Причём, в формуле эффекта логическими связками могут быть только конъюнкции и отрицания, а в предусловии – только конъюнкции.
Описание действий:
<actions-def>::= <action>+
<action>::= (:action <name> :parameters ( <list-varibles-with-type> ) :precondition (and <atomic-formula>+ ) :effect (and <atomic-formula>+ )) 
<atomic-formula>::= (not ( <predicate> <variable>* )) | ( <predicate> <variable>* )
Например:
(:action drive
:parameters (?x ?y - location)
:precondition (and(at ?x))
:effect (and (at ?y) (not(at ?x))))
Определена схема действия drive. После идентификатора ‘:parameters’ идёт объявление параметров, нужных для определения действия. Далее идут предусловие и эффект. Предусловие – конъюнкция предикатов. Эффект – конъюнкция предикатов или их отрицаний. Таким образом, действие drive применимо тогда когда в текущем состоянии есть факт (at ?x). Данное состояние действие переводит в состояние с тем же набором фактов, за исключением того, что факт (at ?x) меняется на факт (at ?y).
Условие применения действия к состоянию определяется так: если формула предусловия выводима из формулы состояния, то действие применимо. Действие переводит данное состояние в состояние, определяемое формулой эффекта: все те предикаты, которые связаны в формуле с остальными логической связкой отрицания, удаляются из состояния, другие же, при отсутствии в формуле состояния, - добавляются. Так строится новое состояние из предыдущего.
Задачи представляют собой набор объектов определённых в домене типов, начальное состояние и конечное. Состояние – формула над определёнными в домене предикатами над множеством заданных объектов; при этом, логической связкой в данной формуле может быть лишь конъюнкция. Ниже представлена часть РБНФ для описания задач. Объявление объектов:
<list-objects>::= (:objects <objects-types>+ )
<objects-types>::=<object>+ - <type>| (either <type>+ )
<object>::=<name>
Например:
 (:objects
soil water rock - data
alpha beta gamma - location)
 Определены объекты soil, water, rock типа data и alpha, beta, gamma типа location. Использование идентификатора ‘either’ нужно для определения объектов, которые относятся к разным типам.
 Начальное состояние и целевое:
<list-init>::=’(:init’ <list-predicates-initialization >+ ‘)’
<list-predicates-initialization>::=’(‘ <predicate> <object>* ‘)’
<list-goal>::=’(:goal (and’ <list-predicates-initialization >+ ‘))’
 Например:
 (:init (at alpha)
(avail soil alpha)
(avail rock beta)
(avail water gamma))
(:goal (and 
(comm soil)
(comm water)
(comm rock)
(at alpha)))
Здесь задаётся начальное состояние, состоящее из фактов (at alpha), (avail soil alpha), (avail rock beta), (avail water gamma). Соответственно задаётся целевое состояние.


Работа планировщика: поиск плана решения задачи происходит в простаранстве состояний прямым ходом или попеременно прямым.обратным с использованием эвристсической информации, извлекаемой из графа планирования, что строится для каждого рассматриваемого состояния в пространстве состояний. За счёт этой информации происходит уменьшение объёма перебора. АЛгоритм построения графа планирования несколько изменён, как и алгоритм работы с пространством состояний (за основу тут взят алгоритм А*).

Далее идут примеры построенных графов планирования и пространства состояний.

Граф планирования для задачи о Ханойских башнях (8 штук):

 

 Граф пространства состояний для задачи логистики:

 Граф планирования для задачи логистики:

Граф планирования для задачи с вездеходом:

Графы пространств состояний для задачи с роботом:

 

 

 

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

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

  Использовать данный текст можно только в ознакомительных целях.

 








Rambler's Top100 Рейтинг@Mail.ru

mdls.ru © 2008-2013

НОВОСТИ
03.04.2014
Проект "ЧПУ на Ардуино" перенесён на ecnc.ru
Открытый проект "Простой станок с ЧПУ на Ардуино" перенесён на http://ecnc.ru
25.01.2013
Опубликован сайт "Частный переводчик"
Частный переводчик поможет провести переговоры, осуществит последовательный, синхронный, письменный переводы. http://tran.mdls.ru
25.01.2013
Начата раработка открытого проекта "Станок с ЧПУ"
Как сделать простой станок с ЧПУ на базе Arduino стоимостью менее 100$ своими руками. http://cnc.mdls.ru.
25.10.2011
"Юристы помогают" перенесён на lawshelp.ru
Проведена смена домена urist.mdls.ru на lawshelp.ru. Теперь обсудить задачи из любых отраслей Права можно на сайте www.lawshelp.ru