Planiranje in razporejanje opravil

Predstavitev problema

Plan: zaporedje akcij, ki pripelje od začetnega do končnega stanja
Formalni opis problema:

začetno in ciljna stanje
akcije - predpogoji in učinki
predpostavka zaprtega sveta: vsa neomenjena dejstva niso resnična, akcija nima neomenjenih učinkov

Predstavitev s formalnim jezikom: STRIPS (1971) - ADL (1986) - PDDL (2005)

STRIPS

akcija(Spremenljivka_1, Spremenljivka_2, ...)
predpogoji: [atom(Argument_1, ...), ...]
učinki:
    add: [atomi ...]
    del: [atomi ...]
omejitve: [trditve ...]

Rezultat akcije $a$ v stanju $s$ : $s_{1} = (s - d e l (a)) \cup a dd (a)$

PDDL

Akcija(spremenljivka_1, spremenljivka_2, ...)
PRECOND: Atom_1(argument_1, ...) AND Atom_2 ...
EFFECT: Atomi ...

Klasično preiskovanje prostora stanj

Uporaba preiskovalnih algoritmov $\to$ možna uporaba akcij, ki niso relevantne $\to$ kombinatorična eksplozija stanj
Rešitve:

dobra hevristika
drugačen pristop k preiskovanju

Planiranje s sredstvi in cilji

Algoritem:

Izberi nerešen cilj
Izberi akcijo, ki lahko vzpostavi (doseže) ta cilj
Ker ima akcija predpogoje, omogoči akcijo z izvedbo predpogojev
Izvedi akcijo
Ponavljaj, dokler niso uresničeni vsi cilji

Sussmanova anomalija

Problem interakcije med cilji
Linearno reševanje: algoritem planiranja obravnava cilje “lokalno” - med reševanjem enega se ne ozira na druge
$\to$ z doseganjem enega cilja lahko razveljavi že dosežene cilje / predpogoje zanje
$\to$ vrstni red obravnavanja ciljev vpliva na nepotrebne korake
Princip varovanja / ščitenja ciljev: pri preiskovanju ne podiramo že doseženih ciljev
Rešitev:

nelinearno planiranje - ne vztrajamo pri urejenosti ciljev
regresiranje ciljev - drugačen algoritem

Planiranje z regresiranjem ciljev

Globalno planiranje: algoritem obravnava vse cilje hkrati
$\to$ obravnavamo najbolj smiselne akcije
Algoritem:

Izberi akcijo, ki doseže čim večjo množico ciljev
Izračunaj predhodne cilje ob uporabi te akcije - regresiranje ciljev skozi akcijo
Analiziramo: veljavnost množice ciljev glede na postopek regresiranja, protislovja v regresirani množici ciljev
$R e g res i r ani c i l ji = c i l ji \cup p re d p o g o ji (A) - a dd (A)$
Veljati mora $c i l ji \cap d e l (A) = \emptyset$
Ponavljaj z regresiranjem, dokler niso uresničeni vsi cilji začetnega stanja ( $re g res i r ani c i l ji \subseteq c i l ji z a \overset{c}{ˇ} e t n e g a s t anja$ )

Razporejanje opravil

Omejitve realnosti:

časovne omejitve: začetki in trajanja aktivnosti, roki zaključkov
omejitve resursov: npr. omejeno št. procesorjev, kadra, bencina, …

Definicijo problema razširimo z:

potrebnim vrstnim redom akcij ( $A k c ija 1 < A k c ija 2$ )
trajanjem operacij
št. razpoložljivih resursov
količina (trajne) porabe resursov ob akciji
količina (začasne) zasedenosti resursov med akcijo

Časovne omejitve

Metoda kritične poti: najdaljša pot določa dolžino trajanja celotnega plana
Vsaki akciji priredimo par [ES, LS]:

ES (Earliest Start) … najbolj zgoden možen začetek
LS (Latest Start) … najbolj pozen možen začetek

Postopek računanja:

ES (St a r t) ES (B) L S (F ini s h) L S (A) rezer v a = 0 = ma x_{A < B} [ES (A) + D u r a t i o n (A)] = ES (F ini s h) = mi n_{A < B} [L S (B) - D u r a t i o n (A)] = L S - ES

Časovna zahtevnost: $O (N b)$ ; $N$ … št. akcij, $b$ … faktor vejanja

Omejitve resursov

Neprekrivanje aktivnosti, ki potrebujejo iste resurse
Časovna zahtevnost: NP-težek problem

Algoritem najmanjše časovne rezerve: hevristka

Na vsaki iteraciji dodeli najbolj zgodnji možen začetek akciji z izpolnjenimi predhodniki in najmanjšo časovno rezervo
Posodobi [ES, LS] za cel graf
Ponavljaj do uresničitve vseh ciljev

SubNotes

Explorer