Лични средства
Вие сте тук: Начало Members marian's Home Експертни системи Примери и упражнения Пример за конструктивно решаване на задачи

Пример за конструктивно решаване на задачи

— Plain Text, 7Kb

Съдържание на файла

;; Running Errands (Least Commitment Strategy)

;; The following CLIPS program schedules an errand
;; by first fixing its start time as early as possible,
;; and then fixing its end time, if a start time has been found.
;; It prioritizes tasks and tries to keep its options open
;; for as long as possible.  However, it is not able to recover 
;; from bad decisions, either by backtracking or by fixing
;; a partial schedule that will not work out.

;; TEMPLATES

;; An errand has a name, an interval in which it must start,
;; defined by earliest and latest, a duration, a priority
;; (low number is high priority), and a symbol that says
;; whether it not it has been scheduled
(deftemplate errand
 (slot name (type SYMBOL))
 (slot earliest (type INTEGER) (default 0))
 (slot latest (type INTEGER) (default 0))
 (slot duration (type INTEGER) (default 100))
 (slot priority (type INTEGER) (default 0))
 (slot done (type SYMBOL) (default no))
)

;; A schedule item has a task, which is the name of an errand,
;; start and finish times, a priority, and a status that says
;; whether or not it has been completely specified
(deftemplate schedule
 (slot task (type SYMBOL))
 (slot start (type INTEGER) (default 0))
 (slot finish (type INTEGER) (default 0))
 (slot priority (type INTEGER) (default 0))
 (slot status (type INTEGER) (default 0))
)

;; The goal template is used to control the behavior of the program
;; by enforcing a certain order in which goals are achieved.  Start
;; times of errands are fixed first, then end times are filled in.
(deftemplate goal
 (slot subgoal (type SYMBOL)))

;; FACTS

(deffacts the-facts
 (goal (subgoal start))
 (errand (name hospital)
	(earliest 1030) (latest 1030) (duration 200) (priority 1))
 (errand (name doctor)
	(earliest 1430) (latest 1530) (duration 200) (priority 1))
 (errand (name lunch)
	(earliest 1130) (latest 1430) (duration 100) (priority 2))
 (errand (name guitar-shop)
	(earliest 1000) (latest 1700) (duration 100) (priority 3))
 (errand (name haircut)
	(earliest 900) (latest 1700) (duration 30) (priority 4))
 (errand (name groceries)
	(earliest 900) (latest 1800) (duration 130) (priority 5))
 (errand (name dentist)
	(earliest 900) (latest 1600) (duration 100) (priority 2))
)

;; FUNCTIONS

;; Does start time S occur in the interval [T, T+D]?
;; Note that no two tasks can start at the same time.
(deffunction overlap1 (?s ?t ?d)
 (and (<= ?t ?s) (< ?s (+ ?t ?d))))

;; Does end time S occur in the interval [T, T+D]?
;; Note that since we assume instant transition from
;; one task to another, Task A can start on B's end time.
(deffunction overlap2 (?s ?t ?d)
 (and (< ?t ?s) (< ?s (+ ?t ?d))))

;; Clumsy addition for times represented as integers according to
;; the 24-hour clock, e.g., 900, 1030, etc.  We assume that
;; all times are already rounded to ten minute intervals.
(deffunction +t (?X ?Y)
 (bind ?T (+ ?X ?Y))
 (if 
    (or (= (- ?T 60) (* (div (- ?T 60) 100) 100))
        (= (- ?T 70) (* (div (- ?T 70) 100) 100))
        (= (- ?T 80) (* (div (- ?T 80) 100) 100))
        (= (- ?T 90) (* (div (- ?T 90) 100) 100))
        (and (<> ?X (* (div ?X 100) 100)) (= ?T (* (div ?T 100) 100))))
  then (+ ?T 40)
  else ?T))
	
;; RULES

;; Certain tasks have to be performed at a fixed time, so we anchor them 
;; right away.
(defrule fixed
 (declare (salience 80))
 (goal (subgoal start))
 ?E <- (errand (name ?N)
	(earliest ?T) (latest ?T) (duration ?D) (priority ?P) (done no))
 (not (schedule (start ?U1&:(overlap1 ?U1 ?T ?D))))
 (not (schedule (finish ?U2&:(overlap2 ?U2 ?T ?D))))
 =>
 (printout t crlf "Fixing start and end of " ?N crlf)
 (modify ?E (done finish))
 (assert (schedule (task ?N)
	(start ?T) (finish (+t ?T ?D)) (priority ?P)))
)

;; Next we schedule highest priority task at its earliest time,
;; if we can do so without clashing with any fixed task.
(defrule priority1
 (declare (salience 50))
 (goal (subgoal start))
 ?E <- (errand (name ?N) (earliest ?T) (duration ?D) (priority ?P))
 (not (errand (priority ?Q&:(< ?Q ?P)) (done no)))
 (not (schedule (start ?U1&:(overlap1 ?U1 ?T ?D))))
 (not (schedule (finish ?U2&:(overlap2 ?U2 ?T ?D))))
 =>
 (printout t crlf "Fixing start of " ?N crlf)
 (modify ?E (done start))
 (assert (schedule (task ?N) (start ?T) (priority ?P)))
)

;; Next we advance the earliest time of any task that cannot be 
;; started at its earliest time, because such a start would lead it
;; to overlap with the start of a scheduled task.
(defrule priority2
 (declare (salience 60))
 (goal (subgoal start))
 ?E <- (errand (name ?N)
	(earliest ?T) (duration ?D) (priority ?P) (done no))
 (not (errand (priority ?Q&:(< ?Q ?P)) (done no)))
 (schedule (task ?M) (start ?U&:(overlap1 ?U ?T ?D)))
 (errand (name ?M&~?N) (duration ?C))
 =>
 (printout t crlf ?N " overlaps with start of " ?M crlf)
 (modify ?E (earliest (+t ?U ?C)))
)

;; We also advance the earliest time of any task that cannot be 
;; started at its earliest time, because such a start would lead it
;; to overlap with the end of a scheduled task.
(defrule priority3
 (declare (salience 60))
 (goal (subgoal start))
 ?E <- (errand (name ?N) (earliest ?T) (priority ?P) (done no))
 (errand (name ?M&~?N) (duration ?C))
 (schedule (task ?M) (start ?U&:(overlap1 ?T ?U ?C)))
 =>
 (printout t crlf ?N " overlaps with end of " ?M crlf)
 (modify ?E (earliest (+t ?U ?C)))
)

;; We also advance the earliest time of any task that cannot be
;; started at its earliest time, because such a start would lead it
;; to begin and end within the scope of a scheduled task.
(defrule priority4
 (declare (salience 60))
 (goal (subgoal start))
 ?E <- (errand (name ?N)
	(earliest ?T) (duration ?D) (priority ?P) (done no))
 (errand (name ?M&~?N) (duration ?C))
 (schedule (task ?M)
	(start ?U&:(<= ?U ?T)) (finish ?F&:(<= (+ ?T ?D) ?F)))
 =>
 (printout t crlf ?N " would occur during " ?M crlf)
 (modify ?E (earliest (+t ?U ?C)))
)

;; We change the goal to establishing the finish times of tasks.
(defrule change-goal
 ?G <- (goal (subgoal start))
 =>
 (modify ?G (subgoal finish))
)

;; A task's finish time is its start time plus its duration.
(defrule endpoint
 (goal (subgoal finish))
 (errand (name ?N) (latest ?L) (duration ?D))
 ?S <- (schedule (task ?N) (start ?T&:(<= ?T ?L)) (finish 0))
 =>
 (printout t crlf "Fixing end of " ?N crlf)
 (modify ?S (finish (+t ?T ?D)))
)

;; The goal is now to report the plan.
(defrule unfinish
 ?G <- (goal (subgoal finish))
 =>
 (modify ?G (subgoal report))
)

;; Tasks are printed out in chronological order.
(defrule scheduled
 (declare (salience 10))
 (goal (subgoal report))
 ?S <- (schedule (task ?N) (start ?T1) (finish ?T2&~0) (status 0))
 (not (schedule (start ?T3&:(< ?T3 ?T1)) (status 0)))
 =>
 (printout t crlf ?N " from " ?T1 " till " ?T2 crlf)
 (modify ?S (status 1))
)

;; Certain tasks may be left over
(defrule unscheduled
 (goal (subgoal report))
 ?S <- (schedule (task ?N) (finish 0) (status 0))
 =>
 (printout t crlf ?N " not scheduled." crlf)
 (modify ?S (status 1))
)

Действия към документ