Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
23
PAGE 19
Модели планирования действий в системах искусственного интеллекта
Лекция 20
Задача планирования. Язык описания состояний и действий. Планирование на основе поиска в пространстве состояний.
Планированием называется процесс выработки последовательности действий, позволяющих достичь цели.
Будем рассматривать среду классического планирования, которая является полностью наблюдаемой, детерминированной, конечной, статической (изменения происходят только в результате действий агента) и дискретной (по времени, действиям, объектам и результатам).
Задача планирования
Рассмотрим использование обычного агента, решающего задачи с помощью стандартных алгоритмов поиска. Такой агент при решении задачи планирования сталкивается со следующими проблемами.
1. Наличие огромного количества действий, не относящихся к делу.
Например, при решении задачи покупки одного экземпляра книги с 10-цифровым номером ISBN, агент-покупатель, осуществляющий одно действие на каждый возможной номер ISBN, должен исследовать результаты 10 миллиардов действий. С другой стороны, если агент имеет информацию о том, что его цель Have(1234567890) и о том, что действие Buy(x) приводит к результату Have(x), то агенту-планировщику достаточно единственного шага унификации, чтобы определить, что правильным действием является Buy(1234567890).
2. Определение хорошей эвристической функции.
Рассмотрим задачу планирования покупки 4-х разных книг. Общее количество планов будет составлять величину 1040. Цель для данной задачи можно представить как конъюнкцию Have(A)&Have(B)&Have(C)&Have(D). Здесь имеет смысл использовать в качестве эвристической функции количество невыполненных коньюнктов. Тогда состояние, содержащее выражение Have(А)&Have(C) будет иметь стоимость 2.
3. Возможность декомпозиции задачи.
Например, в наихудшем случае время, необходимое для поиска наилучшего плана доставки n пакетов экспресс-почты адресатам, разбросанным по всей России составит величину O(n!). Если же использовать декомпозицию задачи на независимые подзадачи в соответствии с ближайшим к каждому адресату аэропортом, то время уже составит величину O((n/k)!*k).
Язык описания состояний и действий
Способ представления задач планирования (состояний, действий и целей) должен обеспечивать возможность для алгоритмов планирования воспользоваться логической структурой задачи. Возможности языка среды CLIPS достаточны для этих целей.
Рассмотрим описание задачи планирования на примере одной из наиболее широко известных проблемных областей планирования, известной под названием мира блоков.
Эта проблемная область состоит из множества блоков кубической формы, находящихся на столе. Блоки можно укладывать в столбик, но на верхней поверхности одного блока может быть непосредственно размещен только один блок. Робот может брать манипулятором только один блок и перемещать его либо на стол, либо на верхнюю поверхность другого блока. Цель заключается в построении одного или нескольких столбиков из блоков. Например, задача может состоять в том, чтобы поставить блок B на блок C и блок A на блок B.
Представление состояний. В планировщиках применяется декомпозиция мира на логические условия, а состояние представляется в виде конъюнкции положительных литералов или, на языке CLIPS, в виде совокупности выражений с синтаксисом представления фактов. Например, для указания на то, что блок B находится на блоке x, где x – либо другой блок, либо стол, используется конструкция on (up B)(down ?x), построенная на основе и шаблона on для двух неупорядоченных фактов (up B) и (down ?x), где переменная ?x может принимать значение либо Table, либо имя другого блока.
Представление действий. Любая схема совокупности действий задается на CLIPS в терминах правила, состоящего из антецедента - совокупности предусловий - условных элементов (УЭ), которые совместно должны соблюдаться до того, как совокупность действий может быть выполнена, и консеквента – собственно совокупности действий, переводящих задачу в новое состояние. Например, схему совокупности действий, состоящих в переносе блока B с блока A на блок С можно записать следующим образом:
(defrule move
?onBA <- (on (up B)(down A))
=>
(assert (on (up B)(down C)))
(retract ?onBA)
)
Представление целей. Цель – это частично заданное состояние, представленное в виде конъюнкции положительных базовых литералов. Состояние s удовлетворяет цели g, если s содержит все атомы из g (и, возможно, другие атомы). Например, цель построения столбика из трех блоков, в котором блок A стоит на блоке B, а блок B на блоке С, находящемся на столе, может быть представлена совокупностью двух правил:
(defrule init-system
(initial-fact)
=>
(assert (goal(current-task find)))
)
(defrule finish-process
(on (up A)(down B))
(on (up B)(down C))
(on (up C)(down Table))
?goal-ptr <- (goal (current-task find))
=>
(retract ?goal-ptr)
)
Под решением для задачи планирования будем понимать последовательность действий, которая будучи выполненной в начальном состоянии (initial-fact), приводит к состоянию, удовлетворяющему цели.
Схема совокупности действий, позволяющих переместить блок b с блока x на блок y, если свободны верхние поверхности и блока b, и блока y, представлена правилом move. После выполнения этой совокупности верхняя поверхность блока x свободна, а блока y – нет.
(defrule move
?onbx <- (on (up ?b)(down ?x))
(clear (name-clear ?b))
?cleary <- (clear (name-clear ?y))
(goal (current-task find))
=>
(assert (on (up ?b)(down ?y)))
(assert (clear (name-clear ?x)))
(retract ?onbx)
(retract ?cleary)
)
Здесь используется новый шаблон clear для представления на его основе состояний свободной верхней поверхности блока b (clear (name-clear ?b)) и блока y (clear (name-clear ?y)), входящих в состояние-предусловие совокупности, и действия добавления в базу знаний факта свободной верхней поверхности блока x (assert (clear (name-clear ?x))). Если ?x=Table, то результатом этого действия будет факт clear (name-clear Table)), но поверхность стола не должна становиться свободной (поскольку она и так всегда свободна), а если ?y=Table, то совокупность действий имеет УЭ (clear (name-clear Table)), но вся поверхность стола не обязана быть свободной для того, чтобы на нее можно было поместить блок (поскольку на столе всегда и без того достаточно места). Для исправления такого положения необходимо предусмотреть два изменения. Во-первых, введем еще одно правило для перемещения блока b с блока x на стол:
(defrule movetotable
?onbx <- (on (up ?b)(down ?x))
(clear (name-clear ?b))
(goal (current-task find))
=>
(assert (on (up ?b)(down Table)))
(assert (clear (name-clear ?x)))
(retract ?onbx)
)
Во-вторых, примем интерпретацию условного элемента (clear (name-clear ?b)) как означающую, что “на b есть достаточно места, чтобы поместился один блок”. При этой интерпретации УЭ (clear (name-clear Table)) всегда будет истинным. Для реализации этой интерпретации включим факт (clear (name-clear Table)) в начальный список фактов.
Единственная проблема состоит в том, что ничто не будет препятствовать планировщику использовать правило move с ?y=Table вместо правила movetotable. Можно смириться с этой проблемой (она приводит к созданию пространства поиска с размерами больше необходимого, но не становится причиной получения неправильных результатов) или ввести в антецедент move условные элементы на основе шаблона block:
(block (name-block ?b))
(block (name-block ?y))
Наконец, существует проблема фиктивных действий, таких как правило move при ?x=?y, которые должны представлять собой пустую операцию, но имеют противоречивые результаты. Обычно принято игнорировать подобные проблемы, поскольку они редко вызывают выработку неверных планов. Правильный подход состоит в добавлении УЭ-проверок в антецеденты правил, как показано в окончательном описании задачи планирования в мире из 3-х блоков:
(deftemplate on
(slot up (type SYMBOL))
(slot down (type SYMBOL))
)
(deftemplate block
(slot name-block (type SYMBOL))
)
(deftemplate clear
(slot name-clear (type SYMBOL))
)
(deftemplate goal
(slot current-task (type SYMBOL))
)
(deffacts init
(on (up A)(down Table))
(on (up B)(down Table))
(on (up C)(down A))
(block (name-block A))
(block (name-block B))
(block (name-block C))
(clear (name-clear B))
(clear (name-clear C))
(clear (name-clear Table))
)
(defrule init-system
(initial-fact)
=>
(assert (goal(current-task find)))
)
(defrule move
?onbx <- (on (up ?b)(down ?x))
(clear (name-clear ?b))
?cleary <- (clear (name-clear ?y))
(block (name-block ?b))
(block (name-block ?y))
(test (not (eq ?b ?x)))
(test (not (eq ?b ?y)))
(test (not (eq ?x ?y)))
(goal (current-task find))
=>
(assert (on (up ?b)(down ?y)))
(assert (clear (name-clear ?x)))
(retract ?onbx)
(retract ?cleary)
)
(defrule movetotable
?onbx <- (on (up ?b)(down ?x))
(clear (name-clear ?b))
(block (name-block ?b))
(block (name-block ?x))
(test (not (eq ?b ?x)))
(goal (current-task find))
=>
(assert (on (up ?b)(down Table)))
(assert (clear (name-clear ?x)))
(retract ?onbx)
)
(defrule finish-process
(declare (salience 1000))
(clear (name-clear A))
(on (up A)(down B))
(on (up B)(down C))
(on (up C)(down Table))
?goal-ptr <- (goal (current-task find))
=>
(retract ?goal-ptr)
(printout t "Solution found" crlf)
)
При использовании стратегии “вширь” (breadth) в среде CLIPS решением данной задачи является следующий план, который в среде CLIPS можно отследить также средствами трассировки выполнения программы (Execution/Watch, Execution /Step, Window/Facts):
movetotable(on(C A)&clear(C)
=>assert(on(C Table))&assert(clear(A)&retract(on(C A)))
move(on(C Table)&clear(B)&clear(C)
=>assert(on(B C))&retract(on(B Table)) &retract(clear(C)))
move(on(B C)&clear(A)&clear(B)
=>assert(on(A B))&retract(on(A Table)) &retract(clear(B))).
Рассмотрим описание задачи планирования еще на одном примере – задаче организации перевозок с помощью воздушного грузового транспорта, в которой предусматривается загрузка и разгрузка грузов в самолеты и из самолетов, а также перелет из одного места в другое. Эта задача может быть определена с помощью трех правил: load, unload, fly. Их совокупности действий влияют на значения двух предусловий - условных элементов: УЭ (in (c ?c)(p ?p)) означает, что груз ?c находится в самолете ?p, а УЭ (at (x ?x)(a ?a)) означает, что объект ?x (самолет или груз) находится в аэропорту ?a.
Ниже приведена полная реализация задачи организации перевозок на языке CLIPS:
(deftemplate in
(slot c (type SYMBOL))
(slot p (type SYMBOL))
)
(deftemplate at
(slot x (type SYMBOL))
(slot a (type SYMBOL))
)
(deftemplate cargo
(slot name-cargo (type SYMBOL))
)
(deftemplate plane
(slot name-plane (type SYMBOL))
)
(deftemplate airport
(slot name-airport (type SYMBOL))
)
(deftemplate goal
(slot current-task (type SYMBOL))
)
(deffacts init
(at (x C1)(a SFO))
(at (x C2)(a JFK))
(at (x P1)(a SFO))
(at (x P2)(a JFK))
(cargo (name-cargo C1))
(cargo (name-cargo C2))
(plane (name-plane P1))
(plane (name-plane P2))
(airport (name-airport JFK))
(airport (name-airport SFO))
)
(defrule init-system
(initial-fact)
=>
(assert (goal(current-task find)))
)
(defrule load
?atca <- (at (x ?c)(a ?a))
(at (x ?p)(a ?a))
(cargo (name-cargo ?c))
(plane (name-plane ?p))
(airport (name-airport ?a))
(goal (current-task find))
=>
(assert (in (c ?c)(p ?p)))
(retract ?atca)
)
(defrule unload
?incp <- (in (c ?c)(p ?p))
(at (x ?p)(a ?a))
(cargo (name-cargo ?c))
(plane (name-plane ?p))
(airport (name-airport ?a))
(goal (current-task find))
=>
(assert (at (x ?c)(a ?a)))
(retract ?incp)
)
(defrule fly
?atpfrom <- (at (x ?p)(a ?from))
(in (c ?c)(p ?p))
(plane (name-plane ?p))
(cargo (name-cargo ?c))
(airport (name-airport ?from))
(airport (name-airport ?to))
(test (not (eq ?from ?to)))
(goal (current-task find))
=>
(assert (at (x ?p)(a ?to)))
(retract ?atpfrom)
)
(defrule finish-process
(declare (salience 1000))
(at (x C1)(a JFK))
(at (x C2)(a SFO))
?goal-ptr <- (goal (current-task find))
=>
(retract ?goal-ptr)
(printout t "Solution found" crlf)
)
Следующий план, полученный в среде CLIPS при использовании стратегии “вширь” (breadth), является решением данной задачи:
load(at(C1 SFO)&at(P1 SFO)
=>assert(in(C1 P1))&retract(at(C1 SFO)))
load(at(C2 JFK)&at(P2 JFK)
=>assert(in(C2 P2))&retract(at(C2 JFK)))
fly(at(P1 SFO)&in(C1 P1)
=>assert(at(P1 JFK))&retract(at(P1 SFO)))
fly(at(P2 JFK)&in(C2 P2)
=>assert(at(P2 SFO))&retract(at(P2 JFK)))
unload(in(C1 P1)&at(P1 JFK)
=>assert(at(C1 JFK))&retract(in(C1 P1)))
unload(in(C2 P2)&at(P2 SFO)
=>assert(at(C2 SFO))&retract(in(C2 P2)))
Планирование на основе поиска в пространстве состояний
Наиболее простой алгоритм планирования – поиск в пространстве состояний. Поскольку описания действий в задаче планирования определяют и антецеденты правил, и их консеквенты, существует возможность организовать поиск в обоих направлениях, либо в прямом, от начального состояния, либо в обратном, от цели. Кроме того, явные представления действий и целей могут использоваться для автоматического вывода эффективных эвристик.
Первый подход, поиск в прямом направлении, часто называют прогрессивным планированием. Планировщик начинает с начального состояния задачи и рассматривает последовательности действий до тех пор, пока не находит последовательность, позволяющую достичь целевого состояния.
Действиями, применимыми в некотором состоянии, являются такие совокупности действий, для которых их УЭ, составляющие антецеденты соответствующих правил, удовлетворяются. Состояние-преемник, являющееся результатом выполнения совокупности действий, вырабатывается путем добавления положительных литералов результата (фактов, добавляемых к базе знаний оператором assert) и удаления отрицательных литералов результата (фактов, удаляемых из базы знаний оператором retract) с возможным применением унификатора из антецедентов. Такая функция определения состояния-преемника является единственной. После выработки каждого нового состояния осуществляется проверка, удовлетворяет ли текущее состояние цели.
При отсутствии функциональных символов пространство состояний задачи планирования является конечным, поэтому алгоритмом планирования может быть любой алгоритм поиска в графе, который является полным.
На эффективность прямого поиска влияют следующие факторы:
− при прямом поиске рассматриваются все действия, применимые из каждого состояния, в том числе и действия, не относящиеся к делу;
− без хорошей эвристики прямой поиск приводит к чрезмерному увеличению объема вычислений. Например, при решении задачи воздушных грузовых перевозок с 10 аэропортами, где в каждом аэропорту имеется 5 самолетов и 20 единиц груза, с целью перемещения всех грузов из аэропорта A в аэропорт B образуется дерево поиска, имеющее около 100041 узлов.
Основным преимуществом обратного поиска (регрессивного планирования) является то, что он позволяет рассматривать только релевантные действия, то есть действия, которые достигают хотя бы одного из конъюнктов цели. Например, целью задачи по перевозке грузов с 10 аэропортами была доставка 20 единиц груза в аэропорт B, а именно:
at(C1 B)&at(C2 B)&…&at(C20 B)
Рассмотрим конъюнкт at(C1 B). Двигаясь в обратном направлении можно найти только одно действие (правило), имеющее в консеквенте такой конъюнкт в операторе assert:
unload(in(C1 ?p)&at(?p B)=>assert(at(C1 B))&retract(in(C1 ?p)))
Имеется много нерелевантных действий, приводящих к целевому состоянию. Если решение существует, то оно должно быть найдено с помощью обратного поиска, допускающего только релевантные действия. Данное ограничение обеспечивает для обратного поиска гораздо более низкий коэффициент ветвления по сравнению с прямым поиском. Например, в данной задаче с грузовыми перевозками количество действий в прямом направлении около 1000, а в обратном только 20.
Кроме того, искомое действие не должно отменять какой-либо конъюнкт цели (быть совместимым). Например, действие load(…=>assert(in(C2 ?p)&retract(at(C2 B))) несовместимо с текущей целью, поскольку оно отменяет конъюнкт at(C2 B) цели.
Опишем общий процесс формирования состояний-преемников для обратного поиска. Пусть для цели G имеется релевантное и совместимое действие A. Состояние-преемник определяется следующим образом:
− любые положительные (assert) результаты действия A, которые имеются в цели G, удаляются;
− добавляется каждый условный элемент из A, если он еще не присутствует в состоянии-преемнике, с возможным применением подстановки переменных.
Завершение работы происходит после выработки такого описания преемника, которое соответствует начальному состоянию задачи планирования. Например, для рассматриваемой задачи преемник после подстановки может выглядеть следующим образом:
in(C1 P12)&at(P12 B)&at(C2 B)&…&at(C20 B).
Ни прямой, ни обратный поиск не могут быть эффективными без хорошей эвристической функции.
Лекция 21
Планирование с помощью пропозициональной логики.
Планирование с частичным упорядочением. Графы планирования
Данный подход основан на проверке выполнимости логического высказывания, модель которого выглядит примерно так:
Начальное состояние & Все возможные описания действий & Цель
Такое высказывание должно содержать пропозициональные символы, соответствующие каждому возможному проявлению действия. Модель, в которой выполняется это высказывание, должна присваивать значение true действиям, являющимся частью правильного плана, и false – другим действиям. Если задача планирования неразрешима, то данное высказывание будет невыполнимым.
Рассмотрим задачу воздушной транспортировки. В начальном состоянии (время 0) самолет P1 находится в аэропорту SFO, а самолет P2 – в аэропорту JFK:
at(P1,SFO)0 & at(P2,JFK)0 & ¬at(P1,JFK)0 & ¬at(P2,SFO)0
Задача состоит в выработке плана действий для достижения состояния, когда самолет P1 находится в аэропорту JFK, а самолет P2 – в аэропорту SFO.
Пропозициональная запись аксиом состояния-преемника выглядит следующим образом:
at(P1,JFK)1 (at(P1,JFK)0 & ¬Fly(P1,JFK,SFO)0) or (at(P1,SFO)0 & Fly(P1,SFO,JFK)0)
at(P2,SFO)1 (at(P2,SFO)0 & ¬Fly(P2,SFO,JFK)0) or (at(P2,JFK)0 & Fly(P2,JFK,SFO)0)
Здесь, например, символ Fly(P1, SFO, JFK)0 является истинным, если самолет P1 вылетает из аэропорта SFO в аэропорт JFK во время 0.
Чтобы предотвратить выработку планов с недопустимыми действиями, необходимо добавить аксиомы предусловий, которые указывают, что для совершения любого действия требуется, чтобы были выполнены его предусловия. В нашем примере необходимо добавить следующие аксиомы предусловий:
Fly(P1,JFK,SFO)0 => at(P1,JFK)0
Fly(P2,SFO,JFK)0 => at(P2,SFO)0
Предположим, что цель истинна в начальном состоянии, во время T=0. То есть проверяем целевое утверждение:
at(P1,JFK)0 & at(P2,SFO)0
Если попытка окажется неудачной, то повторим ее снова во время T=1, то есть проверим выполнимость высказывания
Начальное состояние & Аксиомы состояния-преемника & Цель1
и т.д. до тех пор, пока не достигнем осуществимого плана с минимальной длиной. Можно наложить верхний предел Тmax для безусловного завершения этого алгоритма. В нашем случае Тmax= 1. После нахождения модели выполнимого высказывания план извлекается путем поиска тех пропозициональных символов, которые относятся к действиям, и которым в модели присвоено значение true. Решением данной задачи является следующий план:
Fly(P1,SFO,JFK)0, Fly(P2,JFK,SFO)0
Добавим еще один аэропорт LAX. Рассмотренные аксиомы состояния-преемника и аксиомы предусловия разрешают самолету вылететь в два аэропорта назначения одновременно! Необходимо ввести дополнительные аксиомы для устранения таких фиктивных решений, которые называются аксиомами частичного исключения действий, предотвращающие одновременное выполнение несовместимых действий. Для рассматриваемой задачи это аксиомы:
¬Fly(P1,SFO,JFK)0 & Fly(P1,SFO,LAX)0
¬Fly(P2,JFK,SFO)0 & Fly(P2,JFK,LAX)0
Вместо аксиом исключения можно использовать аксиомы ограничения состояния, утверждающие, что ни один объект не мог находиться в двух местах одновременно:
для любых p, x,y,t x≠y => (at(p,x)t & at(p,y)t)
В пропозициональной логике необходимо будет записать все базовые экземпляры каждого ограничения состояния.
Итак, планирование в форме доказательства выполнимости предусматривает поиск моделей для высказывания, включающего описание начального состояния, цели, аксиом состояния-преемника, аксиом предусловий, а также либо аксиом исключения действия, либо аксиом ограничения состояния. Можно показать, что эта совокупность аксиом является достаточной, в том смысле, что при их использовании больше не возникают какие-либо “фиктивные решения”. Любая модель, в которой выполняется такое пропозициональное высказывание, будет представлять собой действительный план для первоначальной задачи, а любая линеаризация этого плана будет представлять собой допустимую последовательность действий, которая позволяет достичь цели.
Основным недостатком пропозиционального подхода к решению задач планирования являются размеры пропозициональной базы знаний. которая формируется в процессе решения задачи. Общее количество символов действий ограничено значением:
T*|act|*|O|P,
где |act| - количество схем действий, |O|- количество объектов в проблемной области, P – максимальная арность (количество параметров) любой схемы действий. Количество выражений еще больше. Например, при 10 временных этапах, 12 самолетах и 30 аэропортах полная аксиома исключения действий состоит из 583 миллионов выражений.
Одним из способов преодоления указанного недостатка является процесс расщепления символов. Например, символ действия fly(P1,SFO,JFK)0, арность которого равна 3, можно заменить тремя новыми символами:
Fly1(P1)0 – самолет P1 прилетел во время 0,
Fly2(SFO)0 – аэропортом отправления в этом полете был SFO,
Fly3(JFK)0 – аэропортом назначения в этом полете был JFK.
Теперь требуется только T*|act|*P*|O| символов.
Аналогичные сокращения допускаются в аксиомах предусловия и аксиомах исключения действий. Для описанного выше случая полная аксиома исключения действий сокращается с 583 миллионов выражений до 9360 выражений.
Лекция 22
Планирование действий в реальном мире.
Условное планирование. Непрерывное планирование.
В ряде реальных проблемных областей необходимо указание времени начала и окончания действий. Например, в проблемной области транспортировки грузов может потребоваться знать, когда именно прибывает самолет, перевозящий некоторый груз.
Для выполнения задач планирования производства требуется осуществление ряда работ, каждая из которых состоит из последовательности действий, имеющих определенную продолжительность и требующих определенных ресурсов. Требуется разработка расписания, минимизирующего общее время, требуемое для выполнения всех работ, при соблюдении ограничений на ресурсы.
Рассмотрим упрощенную задачу сборки автомобиля, предусматривающую две работы: сборка автомобилей C1 и C2. Каждая работа состоит из трех действий: установка двигателя, установка колес и проверка результатов. Предположим, что двигатель должен устанавливаться в первую очередь, а проверка, безусловно, должна проводиться в последнюю очередь.
В тексте программы на языке CLIPS, приведенном ниже, используются следующие шаблоны для спецификации неупорядоченных фактов:
engine – спецификация факта начала установки двигателя e на шасси c с плановым временем t,
wheels – спецификация факта начала установки колес w на шасси c за время t,
chassis – спецификация факта использования шасси c,
enginein – спецификация факта окончания установки двигателя на шасси c,
wheelson – спецификация факта окончания установки колес на шасси c,
done – спецификация факта окончания поверки автомобиля, собранного на шасси c.
Правила addengine, addwheels и inspect описывают, соответственно, действия по установке двигателя, колес и проверке.
(deftemplate engine
(slot e (type SYMBOL))
(slot c (type SYMBOL))
(slot t (type INTEGER))
)
(deftemplate wheels
(slot w (type SYMBOL))
(slot c (type SYMBOL))
(slot t (type INTEGER))
)
(deftemplate chassis
(slot c (type SYMBOL))
)
(deftemplate enginein
(slot c (type SYMBOL))
)
(deftemplate wheelson
(slot c (type SYMBOL))
)
(deftemplate done
(slot c (type SYMBOL))
)
(deftemplate goal
(slot current-task (type SYMBOL))
)
(deffacts init
(engine (e E1)(c C1)(t 30))
(engine (e E2)(c C2)(t 60))
(wheels (w W1)(c C1)(t 30))
(wheels (w W2)(c C2)(t 15))
(chassis (c C1))
(chassis (c C2))
)
(defrule init-system
(initial-fact)
=>
(assert (goal(current-task find)))
)
(defrule addengine
(engine (e ?e)(c ?c)(t ?d))
(chassis (c ?c))
(not (enginein (c ?c)))
(goal (current-task find))
=>
(assert (enginein(c ?c)))
(printout t crlf "addengine " ?e " " ?c " " ?d)
)
(defrule addwheels
(enginein (c ?c))
(wheels (w ?w)(c ?c)(t ?d))
(chassis (c ?c))
(goal (current-task find))
=>
(assert (wheelson(c ?c)))
(printout t crlf "addwheels " ?w " " ?c " " ?d)
)
(defrule inspect
(enginein (c ?c))
(wheelson(c ?c))
(chassis (c ?c))
(goal (current-task find))
=>
(assert (done(c ?c)))
(printout t crlf "inspect " ?c " 10")
)
(defrule finish-process
(done (c C1))
(done (c C2))
?goal-ptr <- (goal (current-task find))
=>
(retract ?goal-ptr)
(printout t crlf "Solution found" crlf)
)
Далее показан результат выполнения программы в среде CLIPS с использованием стратегии “в глубину” (depth). Так как действия по сборке обоих автомобилей лишь частично упорядочены, то есть действия, относящиеся к разным автомобилям, могут производиться параллельно, то полученный план можно изобразить так, как показано на рисунке 1. Продолжительность каждого действия обозначена в нижней части каждого прямоугольника, а значения самого раннего и самого позднего времени начала, показаны в верхней левой части.
addengine E1 C1 30
addwheels W1 C1 30
inspect C1 10
addengine E2 C2 60
addwheels W2 C2 15
inspect C2 10
Solution found
Рис.1
Для преобразования этой задачи в задачу составления расписания, необходимо определить, когда должно начаться и закончиться каждое действие, с учетом продолжительности действия, а также их упорядочения. Определив частичное упорядочение действий с учетом их продолжительности, можно применить метод критического пути для выяснения допустимых значений времени начала и окончания каждого действия.
[0,0]
Start
85,85]
Finish
[30,45]
addwheels1
30
[60,75]
inspect1
10
[0,15]
addengine1
30
[75,75]
inspect2
10
[60,60]
addwheels2
15
[0,0]
addengine2
60