Nederlandse organisatie voor toegepast natuutwetenscflappefik onderzaek
*Laboratorium
.
Fysisch en Elektronisch TNO0 Posibvs 96864 2509 JO 's-Gravenhage 63 Oude Waalsdorrperwieg s-Graverrtage
TNO-rapport
Tel foon 070 -32642 21 raipportnummer
exempleflmummr
FEL-91-B317
0
~)
Plan van aanpak voor de bouw van een knowledge based planner
AD-A245 472 worderr Niels citdaze uitgeve meag verenrgnoldrgd en/of operbaw gemaakt microffirm doormxfdo van druk.foctokopie. opvelke andere witzedenook.zoilder of0 vcorafgaande foestermrng van TNO. Metter inzage geven van' net TNO-rapporl ar, dirct belariglebtrenden is toegestsarr
auteirs):
Ing. C.W. d'Huy
Inclen dr!rapportin odraChtwerd uitgebractlt. wordtvco, de reofitenen en verpitrhnrgefl van otpdractrtgever nearde verwvezen opdracthtnemner Algemerie Voorna'arden
voo,
DELE CTI E
Onderzoeks-
datum:
terzake tassn er en genloten
FEB 0
Qktober 1991
ortenkorr
419921
rubnceamg RAPPOR72NCFSTRALE118
!rIDCK
Frederikkazerne, Geb. 140 van den Burchlaan 31 Teefoon: 070-3166394/6395 Telefax :(31) 070-3166202 Postbus 90101 ~ 2509 LS Den Haag
ri
,j nimnt
0
blS ogf
tea pjbliC r,.jpds3# crd Sn~ft its
in
I
samnvatting
ofigerubriceerd
raportakst
oflgeubiceerd
bitlagen Atem F
otigerubriceerd
pa"2
&NOWu~~n
-de
ongerubnceerd
49 (..
a=.
ItP
ho)
92-028-25
ifl~huI192 2 03 164
TNO-raport
2
Rapporriummer
FEL-91 -B317
TOMe
Plan van aanpak voor de bouw van een knowledge based planner
Auteur(s)
Ing. C.W. d'Huy
Ilstuut
Fysisch en Elektronisch Laboratorium TNO
Datum
Oktober 1991
Nr inIWP91
704.2
Samenvatting (ongerubriceerd) In dii plan van aanpak zijn de docistellingen omnschreven, aismede de te vemrchten werkzaamheden en hieruit voortviociende producten. voor de bouw van een knowledge based planner zijnde een combinatie van een time map manager (TMM) en een heuristic task scheduler (HTS).
NTIS
By
01:1t
?t
TNO-rapport
Report no. Tdtl
Plan of actions for the development of aknowledge based planner
Author(s)
C.W. d'Huy
Institute
TNO Physics and Electronics Laboratory
Date
October 1991
No in pow 91
704.2
FEL-91-8317
Abstract (unclassified) This plan of action outlines the goals, activities to be performed and products of the project concerning the development of a knowledge based planner being acombination of a time map manager (TMM) and a heuristic task scheduler (JITS).
TNO-rapport
Pagiia
SAMENVATI'IG
2
ABSTRACr MNOVDSQPGAVE AFIKORTINGEN EN ACRONYMEN
4 6 7
I.INLEIDING
2.2
PROJECTBESCHRUVING Achtergrondefl en historie Probleenistelfing van knowledge based planning
2.3
Doelstelling van de opdracht
2.4
Fasering
2.5
Resultaten
3.
PROJECrORGANISATIE
3.!1
Structuur
4.
PROJECITLANNING
41
Werkpakkettetl
4.2 4.3
NetweALstluctuur Capaciteits- en tijdparniflg
5. 5.1 5.2
KWALIrhIT Stwiduds, meibodet' en hulpmniddelefl Procedures
6.
INVORMATIE EN COMMUNCATIE
6.1
Imtem
6.2
Extem
2. 2.A
8 8 t0 12 14 is 17 17 18 18 18 18 19 19 19 20 20 2D
TNO-rappont-
Pagmna
LITERATUURLUST BIJLAGE A:
WERKPAKKE1TEN
BULAGE B:
WERKPAKKETTENMTUCrUUR
BIJLAGE C:
QRGANISATIESTRUCrUUR
BIJLAGE D:
NETWERKSTRUCTUUR
BIJLAGE E:
CAPACITEITSPLANNING
BIJLAGE F:
TIJDPLANNING
22
TNO-rapporn
Pagina 6
Afkortingen en acronymen CASE
Computer Aided Software Engineering
CCIS
"Command and Control" Informatie Systemen
FEL
Fysisch en Elektronisch Laboratoriuxn
GPS
General Problem Solver
KITS
Heuristic Task Scheduler
KADS
Knowledge Acquisition Documentation and Structuring
KBS
Knowledge Based Systems
KI
Kunstmatige Intelligentie
NIAM
Nijssens Informatie Analyse Methode
NOAH
Nets Of Action Hierarchies
SA
Structured Analysis
SKE
Structured Knowledge Engineering
STRIPS
Stford Research Institute Problem Solver
TMM
Tam Map Mager
TNO
Nederlmdse organissmie voor Toegq,.st Nsuwwetnschqmpdijk Onderoek I"
Vnje Univeritit Amsterdam
r
TNO-rnppon
1.
Inleiding
Dit rapport bevat een plan van aanpak voor de bouw van een knowledge based planner gebaseerd op de time map manager CTMM) en heuristic task scheduler (HTS). De doelstellingen van het project. aismede de daaniit voortvloeiende wertczaamheden en producten warden in dit plan omnschreven. De toepasbaarheid van de planner zal gedernonstseerd worden aan de hand van een case betreffende een reeel planningsprobleem. Het project zal op bet FEL-TNO worden uigevoerd door een student informatica van de Vrije Universiteit Amsterdam, gedurende een periode lopende van begin september 1991 tot eind maart 1992 (28 weken).
*
TNO-rapport
Pagina 8
2.
Projectbeschrijving
2.1
Achtergronden en historie
Een reeds lang bestaand underwerp, binnen geautomatiseerd redeneren is bet ontwerpen van systemen welke een verzameling acties (een plan) kunnen voorschrijven om een bepaald doel (goal) te bereiken. In bet ideale geval wortit de geproduceerde verzameling aan een robot. productiemachine of een andere uitvoerder doorgegeven. welke de acties uitvoert. Centraal bierbij staat dat kennis van en over bet domein waarover gepland wordt, de zoekruimnte waarbinnen de goal zich bevindt drastisch kan beperken. Zulke systemen worden in bet algemeen dan ook knowledge based planners (op kennis gebaseerde planners) genoeznd. Tocpassingsgebieden waaraan men bij knowledge based planning zou kunnen denken zijn: -
* -
robotica (path planning); proves industrie; resource management: commandosysiemen.
Het geheel aan planningsproblemen is te verdelent over een aantal categorieen: -
-
tocwijzen van middelen (resource allocation) zonder tijdsaspecten. toewijzen van middelen met een vast tijdschema (het maken van een rooster); het ordenen van acties in de tijd (scheduling); ontwerpcn.
NB. In het vervoig zullen de termen scheduling en planning door elkwa gebruikt worden. Het planning- / scheduling-ondefzwek is vanaf het begin cen bezigheid geweest bitmen de wereld der kunstmatige uuefligeriie. Dit fesultente begin jaren 70 in systemen &isOPS (general problemn solver) en STRIPS (Stanford Research Intitute Problem Solver).
-A,.
TNO-rappofl
Pagina 9
GPS introduceerde de zgn. means-ends analysis. Een goal plannen betekent een operator toepassen welke de goal 'waar' zal maken. De precondities van de operator verfijnen bet oude goal en warden nieuwe (sub-)goals. STRIPS de opvolger van OPS, relateerde operatoren aan acties in de werkelijke' weteld. De veranderingen die acties aanbrengen in de wereld kunnen gerepresenteerd woitlen door bet toevoegen en verwijderen van feiten uit bet wereidmodel. Vanuit deze basisconcepten evalueerde planningresearch uiteindelijk in 1975 tot Sacerdoci's NOAH (nets of action hierarchies). Allc onr.wikkelde planners voor NOAH gingen uit van cen complete ordening van de acties in de tijd. Wanneer er een nieuwe actie toegevoegd moest worden, dan wist de planner welke acties cr voor moesten komen en welke er na. NOAH verzwakte die aanname, en tiet toe dat sommige accies to.v. elkaar geen ordening kenden. Uiteindelijke volledige ordening werd uitgesteld tot dat punt wanneer deze noodzakelijk werd. Het werken met deze gedeeltelijke ordening gaf NOAH de flexibiliteit die nodig was orn veel onverwachte interacties cussen verschiflende pianningsstappen te vermijden. Sinds NOAH heeft research tLax, planning zich vooral gericht op bet reprcsent,ren van en redeneren met gedeeltellik geordende acties. Het gmtc voordeel van gedecliclijk geordende acties is dus de flexibiliteit. In geheel geordende actienctwerken wordt dc volgorde van taken in een vroeg stadium vastgelegd. Wanneer een onverwachic sub-taak zich voordoet welke een ongewenste interactie oplevert met een andere taak. dan is het veranderen van de taalcvolgorde. zodat deze interactie niet optreedt. vrijwel onniogelijk. Gedeeltelijke ardening laat de planner vrij in het arrangeren van taken. Dit genereert echter oak twee problemen: -
Het consistent houden van het taaknetwerk.
-
Het rekening houden met context afliankelijke beperkingen wordt moeilijker.
In 1985 constnicrde Thomas- Dean zijn TMM (Time Map Manager) welke het mogelifk maaki orm een gedeehielijk geordend! net van taken bli te houden en het consistent te houtien. Dsanast werd. eveneens in 1915. FITS (Heuristic Task Scheduler) gepreaentcerd door David Miller. FITS wenl oreworpen oat cordext afhatftijk it kumien rederwren over een verzaueling taken (in cen geheel geordend netwek). Navolgend onderzoek nardeze twee systen had ala voonawnse conchu
da hoewel die systemen vinjwel complememoar zijn am elkaa. cen combinatic van
be&d (TMM ceme traject. FITS tweede mrac) cen kradwige plt~r zou kuati opevett.
rN~apo Pagina
10
2.2
Probleemstelling van knowledge based planning
Uit voorstudie is gebleken dat de combinatie TMM - fITS een veel belovende planner kan opleveren. Veel onderzoek is hiemaar niet gedaan en vooraisnog lijkt er slechts &-n (academische) realisatie gebouwd te zijn en wel FORBIN: een planner VOOr bet genereren van plannen in domemnen met mabiele robots, deadlines en beperkte resources (1987). Een probleemn waar men in ieder geval op stuit is de vraag waar het overstappunt TMM -> HTS zich bevindt. Wanneer mag cen planner besluiten am van TMM's gedeeltelijk geordende taaknetwerk. cen compleet geordend taaknetwerk te maken zodat fITS hierover kan redeneren? Verdere probleerogebieden in planningonderzoek hebben betrekking op:
-
Truth maintenance / backtracking. Wanneer de planner op een 'daocrpad komt dan zal hij terug moeten springen naar een punt. cerder in het planningsproces, waar een altemnatieve beslissing mogellik is. Eerder gemaakte aficidingen in de dode tak macten ongeldig gemaakt warden. Hicrplanining. Automatisch gcgencreerde planningen kunnen vaak mocilijk (automatisch) gewijzigd worden. Dit betekent dat men over bet algemeen van voren af aan moet beginnen wanneer er nieuwe inforrnatie. over datgene wat gepland dient te warden, beschikbaar komt tildens bet plarmingsproccs. Wanneer de planner in cen omgeving werkt waar onzekedheidsfactoren cnn rol spelen en de uitkomst van acties niet van te varen exact kan warden voorspeld. dienen zich tijdens bet uitvoeztn van het'ode' plan regelmatig nieuwe cq.
*
gewijzigde goals aan. Constant geheel ovemnicuw plannen zou don uit efficientie overwegingen niet altijd nodig macten zijn. Incomplete informatie. Wauuicer men in cen bepaald planningsdamein sicius over incomplete infonnaffie
beschiki. dan zou den reeds als uitganspumt moeten kuruien dienen voor cai tockomsfig plan. In wezen is dit gmseerd umn herplaming. Wawm complete inforade besctkbar kom don zou heupluming van het incomplete plan met de souillende informatie voloenmoten zijn.
TNO-rapport Pagina
-
-
Parallelliseren van het algontme. Er kan hierbij aan twee onderwerpen gedacht worden: "
parallelle implementatie van het normale algoritme uit snelheidswinst
*
overwegingen. gating object. Onderzoek naar wijzigingen in het algoritnie zodat altemnatieven parallel doorzocht kunnen worden (split time maps).
Context- afhankelijke en onafhankelijke kennis. Wat betekent het als de planner domain independent is? Welke problemen ontstaan er wanneer zo'n planner voor een specifiek domain geconfigureerd moet warden? Hoe dienen de domeinkennis en de domein-planningskennis gerepresenteerd te warden?
Niet alle hierbovcn beschreven problenien zullen binnen deze studie beschouwd kunnen warden. In paragraaf 2.3 wordt de docistelling van dit project beschreven en daamiee impliciet oak een beperking t.a.v. de hier beschreven probleemngebieden.
TNO-rapport
Pagina 12
2.3
Doelstelling van de opdracht
Doelstelling van het project is onderzoek doen naar en realisatie van een knowledge based planningssysteein. De eisen aan het systeem zijn: -
Uitgaande van een iniide toestand van de wereld warver geredeneerd wordt, een gewenste toestand (goal) van die wereld en een verzanieling actics, moet een selectie van acties (primitieve taken) uit de venzarneling van alle niogelijke acties gemaakt kunnen worden. Dezc acties dienen logisch geordend in de tijd te zijn en wel op een zodanige manier dat wanneer de acties volgens deze ordening worden uitgevoerd ze de gegeven
initiele toestand transforrneren in de gewenste toestand. * Gecratie van dc selectie en ordening van acties verloopt op basis van TMM en HTS. De planner moet context onafhankelijk zijn. Er moet dus duidelijk een verschil zijn tussen -
domeinafhankelijke en domeinonafhankelijke kennis. De planner moet altematieve plannen kunnen genereren. Waarschijnhjk koint dit neer op cen gedeelteiijke hcrplanning. uitgaande van dc zelt'de basisinforinatie en goals; maar nu
-
met altematieve goal expansies. Dc planner dient zo opgezxet te zijn dat wanneer de te plannen goals veranderen of %N ijzigen. het niet noodzakclijk zo is dat van voren af aan opnieuw gepland dient te worden.
-
*
De planner dient met incompletc informatie he kunnen werken. De planner moet wijzigingen in de planningsgegevens redelik eeciwoudig kunrn opricmen.
Verder Magetracht moeten worden de toepasbaarheid van de verkregen planner aan te tonen in cen reftl domein. aan de hand van een refel planningsprobleem.
TNO-rapport
Pagina 13
De uiteindelijke keuze van functionele / technische mogelijkheden van de planner zal afhangen van de beschikbare tijd binnen het project. Aan het eind van dit project zal cen cindrapport opgesteld worden waarin versiag wordt gedaan van de resultaten van het project. aismede over de evaluatie van het project, Bij dc ev'aluatic za] o.a. aan de volgende criteria aandacbt geschonken worden: -
Is de planner practisch / operationeci inzetbaar. wanneer deze voor een bepaald domein geconfigureerd is" Hierbij kan gedacht worden aan: performance, communicatie tussen planner en gebruiker. practische planningskracht van de planner, welke elsen stelt de planner aan zijn gebruiker. etcetera.
-
*
Is de planner werkelijk dome nonafhankelijk? Of is djt practisch gezien niet mogelijk of wcensclijk" Iseen dergelijke planner eenvoudig te configureren voor een bepaald dornein? Welke eisen stelt hij dan aan diegene die de planner configureert? Kan de planner (automatischi herplannen, zonder gebeel overnieuw te plannen. Zo ja is dit .%zenlijk voor de kracht cq. performance van de planner? Of weegi de effort die in het vinden van cen herplanningspunt gestoken morn worden niet op tegen 'dom weg'van voren a] aan plannen?
-
-
-
Hoc verloopt de samenwerking TMM - HTS? Voldoet deze aan de verwachtingen? Hoe is hct ovcrstappunt gekozen en zijn er altematieven? Biedt de planner mogclijkheden om vast te stellen waarom een planning mislukt is? Gesignalcerde problemen tijdens de bouw. mogelijke verbeteringen. Aanwijzingen Ionderwerpen voor verder onderzoek.
TNO-rapport
Pagmna 14
2.4
Fasering
De opdracht is opgedeeld in de volgende fasen, die grotendeels sequentieel doorlopen zuflen worden: * -
Introductie, Probleemanalyse
-
Ontwerp:
-
Bouw van het planningssysteem; Tocpasbaarheid aantonen door oplossing van een redel planningsprobleem; Evaluatie, discussie;
-
Opstellen cind rapport.
-
Voor cn gederailleerde uitwerking van deze fasen zie bijiagen A en B.
TNO-rapport
Pagana 15
2.5
Resultaten
Op de werkzaamheden en rapportage zijn de voor FEL-TNO geldende beveiligingsvoorschriften voor defensieopdrachten van toepassing. be resultaten van het onderzoek zijn documenten waarin verslag wordt gedaan van de werkzaainheden die in het kader van de werkpakketten zijn uitgevoerd, aismede een implementatie van een knowledge based planner en eventuele tools aangaande deze planner. Dit aflcs wordt saniengevat in een afstudeerverslag dat de basis vormt voor de beoordeling van de student. Dit verslag zal onder andere de volgenide onderwerpen bevatten: -
-
Probleemnanal ysc; Functionele specificaties Ontwerp. Bouw van de planner:
-
Tesfen: Tocpasbaartieidsdemonstratic;
*
Evaluatic.
-
De op te leveren resultaten zijn: -
Plan van aanpak Wdit document); Progranimatuur en systeemdocumentauie: * TMM Time Map Manager, * * * "
*
HTS Heuristic Task Scheduler. De planner (bcsturngsinodule voor TM[M en HTS). Eventuelc tools voor de planner, Een demonstratie configurauie van de planner.
Eindrappon.
Alle rapponen worden ter becommentariering aan de beurokkcnen Wze hoofdstuk 3: proJectorpniaie) verstuurd.
TNO-rapport
Pagina 16
Deze versiagen verschijnen in de vorm van een FEL-rapport met de rubricering '1ongerubriceerd". Aangezien dit. FEL-rapport uisluitend ongeclassificeerde informatie bevat, zijn er gE~n beperkingen ten aanzien van de beschikbaarheid. Tot slot dient te worden opgemerkt dat de resultaten van het onderzoek eigendom blijven van TNO. Zonder voorafgaande schriftelijke toestemnming van TNO is het niet. toegestaan deze resultaten te publiceren of op andere wijze openbaar te doen maken.
TNarap port
Pagina 17
3.
Proj ectorg anisatie
3.1
Strumtur
De organisatiestructuur wordt weergegeven in bijiage C. Vanuit FEL-TNO zullen de volgende medewerkers; dc opdracht begeleiden: -
Drs. H.P. van Qordt (medewerker CCISJKBS)-.
-
Ir. M. de Niel (mcdcwerker CClSKBS).
Vanuit de *Vnjc Universiteit Amsterdam, faculteit der Wiskunde en Informatica, zal het afstuderen begelcid wordcn door: -
Dr. W. Kowalczyk (afstudeerdocent sectie K.Ii.
-
Prof. Dr. J. Treur (supervisor).
TNO-rappofl
Pagmn 18
4.
Projectplanning
4.1
Werkpakketten
Zie bijiagen A en B.
4.2
Netwerkstructuur
Zie bijiage D.
4.3
Capaciteits- en tijdplanning
Zie bijiagen E en F.
TNO-rapport
pagma 19
5.
Kwaliteit
5.1
Standaards, methoden en hulpmiddelen
Documenten zullen conform de TNO-huisstijl warden uitgevoerd met behuip van het tekstbewerkingspakket MS-WORD. De mogeiijk te gebniiken analyse- ,ontwerpmethoden en hulpmiddelen zijn: NIAM, KADS. SKE, SA en de CASE-tool RIDL. Voor de bouw bestaat de keus ui Strand-88 en Quintus Prolog.
5.2
Procedures
Na uitvocring van de werkpakketten 2100, 2200. 2300, 2400 wordt een review gehouden, waarin de tot dan toe bereikte resultaten aan een kritische beschouwing onderworpen zullen warden. Hieniaast vindt er in her kader van de normale begeleiding geregeld werkoverleg plaats.
TNO-rapport
Pagina 20
6.
Informatie en Communicatie
6.1
Intern
Naast de introductie tot het FEL en de te hanteren hulpmiddelen, zal de inteme cammunicatie vaamamelijk bestaan uit werkaverteg cq. voortgangsgesprekkcn en eventuele bijsturing van bet project. Verder zal er averleg gevoerd macten warden mbt. het verkrijgen van'domeinkennis' voor bet bouwen van een planner vor een retel planningsprobleern.
6.2
Extern
De exteme informatie en communicatie icht zich in het algemeen tot de VUJ, faculteit Wiskunde & lntbrmatica, sectie Kunstmatige Intelligentie, en zal vaamnamelijk bestaan uit
regelmatig contact met dc afstudeerdacent. Verder warden de geschreven rapporten (plan van aanpak. af~tudecrscniptic) naar de VU gestuurd.
TNO-rapport
Pagina 21
Di.H.P. van Oordt (Projecticider)
Ing. C.W. d Huy (Auteur)
Ir .de Niet (Begeleider)
Ir. . . Woestenburg (Groepsleider)
TNO-rappon
Pagina 22
Literatuurlijst IAllea83I
Allen, J.F. (1983); Maintaining knowledge about temporal intervals; in communications of the ACM number I I november 1983; pp 832-843.
[Allen9Ol
Allen, J.F., Hendler, J., Tate, A. (editors) (1990); readings in planning; Morgan Kaufmann Publishers, San Mateo, California.
5Cohen)
Cohen, P.R., Feigenbaum, E.A. (1983); The handbook of artificial intelligence, volume III; Department of computer science, Stanford university; Pitnan, pp 1027,475493, 515-562.
[DeanS61
Dean, T.L. (1986); Handling shared resources in a temporal data base management system; in Decision support systems 2; Elsevier science publishers, pp 135-143.
{Dean871
Dean, T.L., McDermott, D.V. (1987); Temporal database management; in Anificial intelligence 32, Elsevier science publishers, pp I - 22.
[Dean881
Dean. T.L., Firby, RJ., Miller, D. (1988); Hierarchical planning involving deadlines, traveltime and resources; in computational intelligence vol. 4, no. 4; Canada, pp 381-398.
lEcki
Eck, I. van (1990); Een ontwerp voor een knowledge based planner; FEL-90-S266.
IFirb.%I
Firby, R.. McDermott, D.V. (1987); Representing and solving temporal planning problems: in N. Cercone and G. McCalla (eds.), The knowledge frontier. Essays in the representation of knowledge, Springer Verlag; New-York, pp 353413.
IGOe)
Ge, Q.. Findler. F.V. (1985); Distributed planning and control for manufacturing Operatons; in Lecture notes in artificial intelligence 406; Springer Verlag, pp 433447.
(Korfl
Korf, R.E. (1987); Planning as search: A quantitative approach; in artificial intelligence 33; Elsevier science publishers, pp 65-88.
ILevil
Levi, P.. Scholz, J (1991); Constraint-guided Scheduling for Satellite Data Processing and Archiving; in Proceedings artificial intelligence and knowledge based systems for space; ESA WPP-025; Noordwijk.
IMifler]
Miller. D. (1985): Planning by search through simulations; Technical rpor 423, Computer science department. Yale ,niversity, New Haven, CT.
IMcDermotlI
McDermott D.V. (1992); A temporal logic for reasoning about processes and plartoimcognitive science 6; pp 101-155
I'Serdil
Sacentoi. E.D. (1977): A structure fi ias and behavior American elsevier publishing onmpany ic.. New York, NY.
TNO-rappOrl Pagila. 23
inSUpPOr I Of (1991): Rownd Table on Artificial Intelligence I~awulVadon. lH..Tae, A. reports; in Proceedings atificial meetings group working planning & Scheduling. fot space-, ESA WPP-025; NocedWilk. intelligenlce and knowledge bWed systemns representtion and plan Domain independent Planning: Wilkins, D.E. (1984); intelligecelC science publishers, pp 269-301. Elsevier 22. 1wilkinl generation-, in artificial
TNO-rapport
Bijiage A
Pn A.]
Bijiage A:
Werkpakketten
TNO-rapport
Bijilage A
Pagina A.2
0000
Knowledge based planning
Het inzicht krijgen in. het bouwen van en rapporteren over een knowledge based planner op, basis van een time map manager (TMM) en een heuristic task scheduler (HTS). Aismede het bouwen van een demonstrator.
I(XX)
Introductic:
NO)0 3000)
Qndcrzock: Rapportage:
4(XX)
Begeleiding.
Prouctn -
* -
FEL-rapporten /ovcrige documentatic; Prolog cq. Strand-88) progr'mmatuur van de planner: Demonstrator. Kennis van knowledge based planning.
TNO~rapport
Bijiage A
Pagina A.3
1000
Introduc tie
DoeItelinL Introductie tot knowledge based planning, begrippen als 'time map manager en 'heuristic task scheduler'. Het eigen maken van methoden en technieken (evt. tools en pakketten) die van belang kunnen zijn bij bet uirvoeren van het project.
-
Voorstudic literatuur;
-
Strand-88 introductic:
*
Quintus Prolog irnroductic:
*
Jn~roduche zoi gebruik van huipmiddelen (practische kennis).
Produan -
Werkplan:
-
Vcrtrouw4dhcid met de in de doelstelling genocmdc methoden en tools,
TNO-rapport
Pagina
Bijilage A
AA4
2000
Onderzoek knowledge based planner
Doesteling lnzicht in en bouw van een knowledge based planner.
A ctietn 2100
Probleemanalyse;
2200 2300)
Ontwerp. Bouw van het systeem:
2400 2500
Toepasbaarheid aantoncn; Evaluatie.
EP n~dc
*
Documenten waarin analyse. ontwerp. bouw en evaluatie zijn vastgelegd; Prograinmatuur waarrnee de planner wordt gerealiseerd;
-
Demonstrator.
-
TNO-rapport
Bijilage A
Pagna A.5
2 100
Probleemanalyse
Dolllig Het verwerven van kennis over knowledge based planning.
Activiiten *
Het verzamelen van informatie mbt. het project. Het doomnemen van relevante Iiteratuur, Het analyseren van TMMIHTS; * Het vastleggen van de resultaten; * Eventuele discussie.
Ecn document betreffende; * TMM en HTS; -
Gesignaleerde problemen en eventuele oplossingen; Overige in de Iiteratuur aangetrffen aandachtspunten.
TNO-rapportS Bijiage A
P ar A.6
Ontwerp
2200
DplseUig Met vastleggen van de functionele specificaties en technisch ontwerp van de planner.
AiititCn -
Opstellen definitie van eisen en functionele specificaties; Ontwerp time map manager: * representatie partial ordered task network. * representatie domeinkennis, " *
-
* protectiemechanisme, afstanden- / consistentiemnechanisme. testcase;
ntwerp task scheduler: representatie completely ordered task network, " heuristic search mechanisme. * representatie domeinafhankelijke beperkingen, 0
"
testcase.
Document met daarin: De cisen en lianctionele specificaties; * let ontwerp. -
TNO-rapport
Pagina A.7
flijiage A
Bouw van het systeem
2300 Doestelin
Bouw van de planner en het testen van de planner.
A~ctitn Keuze Strand-88 vs. Quintus Prolog; Bouw van time map manager,
-
2310 2330
Bouw van task scheduler Bouw knowledge based planner
2340
Testen van het systeem.
2320
Pwdute -
Progranimatuur
(zie 2310, 2320, 2330)
-
Documeniatie
(zie 2310, 2320, 2330, 2340)
TNO-rappon
Dijiage A
Pgn A.8
2310
Bouwen van time map manager
Doestlling Het maken van programmnatuur voor het beheren van een 'partial ordered task network'.
Ativieiten -
Bouw TMM;
-
Testen TMM.
Produte -
Prolog cq. Strand-88 programmatuur,
-
Documentatie.
TNO-rapport
Biffiag A
Pagina A.9
2320
Bouwen van task scheduler
Doelstllina Het maker, van pmogranlrnauur voor het maken van een 'completely ordered task netwod*.
Atviet -
Bouw task scheduler;, Testen task scheduler.
PEdutn Irolog cq. Strand -88 programmatuur P -
Docurnentatic.
TNO-rapport
Wijlage A
Pagina A.10
2330
Bouw Knowledge based planner
Cornbineren van TMM en HTS tot een complete planner.
-
-
-
Koppeling TMM aan HTS; bouw interface mbt: * invoer domeinkennis (expansies), * invoer goals. " uitvoer / representatie van bet gemaakte plan, * cvL diagnose waarom planning misiuki is; Bouw bcsturingsmnodule. interface en tools; Testen planner.
Prouctn -
Prolog cq. Strand-88 Progranimatuur,
-
Evt. tools
-
Documentatic.
A.11I
2340
Testen van het systeem
Test or bet systeem doet wat zou macten doen, zowel functioneed als struictureel. Geen slujistuk maar onderdeel van de implementatie.
-
Functioned testen (black box).
-
Structured testen (white box).
Proucte -
Tcstresultaten.
r
TNO-rappont
Bijilage A
Pagina A.12
2400
Toepasbaarheid aantonen
Het door middel van een reel praktijkprobleem inzicht krijgen in de mogeijkheden en onmogelijkheden van de planner.
*
Bestudenng praktijkproblecm,
*
Vastleggen domeinafbankelijke planningskennis;
-
Opstellen test-case: Uitvoeren planning aan de hand van een test-case,
*
Vastleggen resultaten.
-
Productn -
Versiag met resultaten.
r
TNO-rapport Diiage A
Pagna A.13
2500
Evaluatie
Evaluatie van het project.
-
Het schrijven van een evaiuatierapport met betrekking tot: " " "
doel van het project. criteria uit plan van aanpak. verwaclitingen en bereikie resultaten.
"
discussie. conclusies, aanbevelingen.
Produc -
Een evaluatierapport.
TNO-rapport
Bijiage A
Pagina A.14
3000
Rapportage
Het inforineren van FEL-TNO. VU en andere belangstellenden over het project en haar resultaten.
-
*
Formele rapportage (FEL rapport); Het schrijven van avenige doc'imentatie: * *
plan van aanpak. tussenrapporten,
*
program madocumentatie:
Het houden van een presentatie over het project.
Prouctn
-
*
FEL-rappon hzcvens afstudcerscriptie). Overige documentatte:
-
Presentatic.
TNrapr Bijiage A
Pagina A.15
4000
Begeleiding
Doe2stllino Begeleiden van de werkzaamheden zodat de projectdoelstelling binnen de gestelde ternijn kan worden gerealiseerd.
Acitite~n
*
Formulering van docistelling en afbakening van dc grenzen van het project; Voortgangsbesprekingen; Bijsiuren. adviseren en becommentaritren van de activiteiten;
-
Kwaliteitsbcwaking:
-
-
Bewaken van de planning; Evaluatie van het cindresultaat.
Prdctn *
Begeleiding werkzaamhcden.
TNO-rapport
1Bijlage B
Pagina BAI
Bijiage B:
Werkpakkettenstructuur
q,,
:
i
TNQ-rapport
Bijiage B
Pagina. B3.2
0000 Knowledge based planning
1000 Introducie
nerok leg
bsd
nw-
3000
Rapportage
4000
Begele~ding
TNO-rapport
*
Bijiage B B.3
basead Bledg
O2310 [
Bouw van time map manager
2
230
Bowvan task scheduler
0
23
Beouw KBvane
vn het yte
TNO-rappon
Bijiage C
Pagina CA
Bijiage C: Organisatiestructuur
-ML
-
TNO-rapport
Bijiage C
Pagna C.2
Examencommisie
FEL - TNO Begeleiders
Hoogleraar (supervisor) Afstudeerdocent
Afstudeerder
TNO-rapport
Pagina D.1
Bijiage D
Bijiage D: Netwerkstructuur
F
TNOrtipport
Bijlage D
P*D.2
Project
100C)
Intfocluctle
bh
3000
2 1.106100100 "Slyse
Rapponage
2310 souto 1-0 .p s aqs,
f
2330 80-
2200 0 1.0,9
2320 601* task
systell"
Fl-
2400 Aaftlarwn TooposbashoW
TNO-rappon
FBijiage
E
Pagina E.1I
Bijiage E:
Capaciteitsplanning
TNO-rappoit Bijage E
Pagina
E.2
1000 2100
Introductie Probleemanayse
2 weken
2200 2310
Ontwerp incl. functionele specificaties Bouw van time map manager
1
2320
Bouw task scheduler
I
totaal
2330 2340
Bouw KB-planner combinatie Testen van het systeeni
I
10 weken
2400
Toepasbaarheid aantonen
5 weken
2500 3000
Evaluatie Rapportage ind redactioneel werk
3 weken
3 weken 3 weken
2 weken 28 weken
_Aii
*
TNO-rappon
flijinge F
Pagina F.1
Bijiage F:
Tijdplanning
TNO-rapporr
Dijiage F
pagma
F.2
1991
2100_ 2310_ 2320
_
j
3000
-
-
2199
__[52
01
02 0304 05 0607 0809
1001o2100_
4O
ZZ1111II
10
11
12
13
14
15
UNCLASSIFIED
REPORT DOCUMENTATION PAGE 1 DEFENSE REPORT NUMBER (MOO-NL)
2 RECIPIENT'S ACCESSION NUMBER
TD91-3689 4. PROJECT/TASKIWORK UNIT NO
(MO
L)
3. PERFORMING ORGANIZATION REPORT NUMBER
FEL-91-B317 5.CONTRACT NUMBER
6. REPORT DATE
22728
OCTOBER 1991
7. NUMBER OF PAGES 8 NUMBER OF REFERENCES 50 (INCL 6 APPEND & ROP. EXCL DISTLIST)16
9. TYPE OF REPORT AND DATES COVERED
FINAL REPORT
10. TITLE AND SUBTITLE
PLAN VAN AANPAK VOOR DE BOUW VAN EEN KNOWLEDGE BASED PLANNER (PLAN OF ACTION FOR THE DEVELOPMENT OF A KNOWLEDGE BASED PLANNER) 11 AUTHOR(S)
C.W. D'HUY 12 PERFORMING ORGANIZATION NAME(S) AND ADDRESS(ES)
TNO PHYSICS AND ELECTRONICS LABORATORY. P.O. BOX 96864.2509 JG THE HAGUE OUDE WAALSDORPERWEG 63. THE HAGUE. THE NETHERLANDS 13 SPONSORING/MONITORING AGENCY NAME(S)
TNO DIVISION OF NATIONAL DEFENSE RESEARCH. THE NETHERLANDS 14 SUPPLEMENTARY NOTES
THE PHYSICS AND ELECTRONICS LABORATORY IS PART OF THE NETHERLANDS ORGANIZATION FOR APPLIED SCIENTIFIC RESEARCH 15 ABSTRACT (MAXIMUM 200 WORDS. 1044 POSITIONS)
THIS PLAN OF ACTION OUTLINES GOALS, ACTIVITIES TO BE PERFORMED AND PRODUCTS OF THE PROJECT CONCERNING THE DEVELOPMENT OF A KNOWLEDGE BASED PLANNER BEING A COMBINATION OF A TIME MAP MANAGER (TMM) AND A HEURISTIC TASK SCHEDULER (HITS).
16 DESCRIPTORS
IDENTIFIERS
ARTIFICIAL INTELLIGENCE PLANNING REASONING
TIME MAP MANAGER HEURISTIC TASK SCHED. REASONING ABOUT ACTION KNOWLEDGE BASED PLANNER
SCHEDULING REASONING ABOUT ACTION I 7 SECURITY CLASSIFICATION (OF REPORT)
171bSECURITY CLASSIFICATICN (OF PAGE)
I 7c 8ECURITY CLASS1RCATON (OF ABSTRACT)
UNCLASSIFIED
UNCLASSIFIED
UNCLASSFIED
IST
IUTOtAVA&AkIUTYSTATEMNT
Uf*JIMTED AVAILA8OLJY
17d. SECUITY CL4ASFICATIoI (OF TITLEgM
UNCLASSIED
