8135

Планирование действий в реальном мире. Условное планирование. Непрерывное планирование

Лекция

Информатика, кибернетика и программирование

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

Русский

2015-02-01

45.5 KB

5 чел.

Планирование действий в реальном мире.

Условное планирование. Непрерывное планирование.

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

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

Рассмотрим упрощенную задачу сборки автомобиля, предусматривающую две работы: сборка автомобилей 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

0,15]

addengine1

30

[30,45]

addwheels1

30

[60,75]

inspect1

10

[85,85]

Finish

[0,0]

addengine2

60

[60,60]

addwheels2

15

[75,75]

inspect2

10


 

А также другие работы, которые могут Вас заинтересовать

74963. Осінній натюрморт. Натюрморт як жанр образотворчого мистецтва. Зображення осіннього натюрморту з натури 91.5 KB
  Мета: Ознайомити учнів з різними видами і жанрами образотворчого мистецтва. Провести бесіду про один із жанрів - натюрморт. Вчити дітей малювати натюрморт, передаючи правильне розміщення, розмір, форму, пропорції і колір предметів.
74964. Математичний фестиваль 202.5 KB
  Зацікавити розум дитини, прищепити учневі смак, пристрасть до навчання, інтерес до предмета, активізувати і стимулювати розумову і пізнавальну діяльність, розвивати самостійність і творчість, логічне та образне мислення, математичну мову учнів, через гру інтерес до математики...
74965. Дорогу осилит идущий, а математику - мыслящий 212 KB
  В игре принимают участие 2 команды 9х классов: команда Радиус радостные активные дружные изобретательные умные смелые команда Фигура физически развитые инициативные грамотные умелые развеселые азартные. Команды приветствуют друг друга зрителей объявляя название и расшифровку обривиатуру...
74966. Фалес Мілетський – давньогрецький математик і філософ 277.5 KB
  Мета: ознайомити учнів з фактами біографії Фалеса Мілетського та його внеском у розвиток математики розвивати пізнавальну активність мову творче мислення память виховувати любов до математики. Обладнання: ілюстрації з зображенням Фалеса сонячного затемнення...
74967. Материки Землі 417 KB
  Мета. Продовжувати формувати уявлення про глобус, карту півкуль, уміння читати карту, працювати з нею; Розвивати просторові уявлення, вміння висловлювати свої думки, сформувати уявлення про материки, їх природні умови, особливості рослинного та тваринного світу...
74968. Берегите матерей своих 52.5 KB
  Стихотворение Мать и дети Кто вас детки крепко любит Кто вас нежно так голубит Не смыкая ночью глаз Всё заботится о вас Мама дорогая Колыбель кто вам качает Кто вас песней забавляет Или сказку говорит Кто игрушки вам дарит Мама золотая...
74969. Народний календар юного бджоляра 845 KB
  Це - мед віск квітковий пилок прополіс маточне молочко бджолина отрута. Мета роботи: поглибити знання молоших школярів про різні аспекти бджільництва; сприяти виробленню стійкого інтересу до життя бджіл усвідомленню значення меду та інших продуктів бджільництва в житті людей.
74970. Букварний період 28 KB
  Мета уроку: Ознайомити дітей з буквою «Е», «е» та її звуковим значенням, закріплювати вміння розрізняти функціональне значення звука та букви, розвивати навички звуко-буквенного аналізу слів, формувати навички правильної вимови звуків у словах, збагачувати словниковий запас.
74971. Поняття про синтаксичні одиниці мови 23.5 KB
  Мета уроку: навчити учнів визначати граматичне значення речення дати поняття про присудок та підмет. Завдання уроку: Учити школярів визначати граматичне значення речення; визначати підмет та присудок; перевіряти орфограми слабких позицій звуків у різних частинах слів...