Automatisk planering
Automatisk planering är en del av artificiell intelligens som går ut på att automatiskt konstruera planer. Typiskt sett är planerna till för utförande av exempelvis en robot, UAV eller annan autonom agent. I sammanhanget är en plan en sekvens av handlingar som uppnår ett visst mål. Ett planeringsproblem beskrivs ofta som ett starttillstånd (den fakta som gäller från början i systemet), ett sluttillstånd (den fakta som ska uppnås), samt de handlingar som modifierar det aktuella tillståndet i systemet. De möjliga handlingarna beskrivs i sin tur av de krav som ställs för att handlingen ska kunna genomföras, samt hur handlingen ändrar på det nuvarande tillståndet. Ett program som plockar fram en plan kallas för en planerare.[1]
Klassisk planering
[redigera | redigera wikitext]Inom delområdet som kallas klassisk planering finns följande restriktioner: [2]
- Det finns ett ändligt antal tillstånd i systemet.
- Det går alltid att veta vilket tillstånd ett system befinner sig i.
- Systemet är deterministiskt, det vill säga att genomförandet av en handling alltid leder till ett visst annat tillstånd.
- Systemet är statiskt, det vill säg att systemet inte har någon intern dynamik utan endast kan påverkas av agenten.
- Planeraren hanterar endast begränsade mål, vilka går ut på att man ska ta sig till ett visst (eller något av flera) olika tillstånd, oavsett hur det går till.
- Sekventiell exekvering, det vill säga att handlingarna som planeraren kommer fram till kan utföras i ordning efter varandra.
- Handlingar och tillstånd saknar tid, utan antas genomföras omedelbart.
- Planeraren behöver inte bry sig om eventuella ändringar i systemet under planeringsstadiet, utan en hel sekvens av genomförbara handlingar ska kunna tas fram på förhand.
Om något av dessa krav tas bort så är det inte längre klassisk planering, utan någon utökad variant.
Algoritmer för klassisk planering
[redigera | redigera wikitext]Det finns flera olika algoritmer som går att använda för att hitta planer för problem inom den klassiska planeringen.
- Framåtsökning börjar i starttillståndet och observerar vilka andra tillstånd man kan komma till genom att utföra en handling. Sökningen fortsätter sedan från något av de nya tillståndet, via någon sökstrategi som exempelvis bredd-först-sökning eller A*. Sökningen avslutas när en sekvens av handlingar som leder till ett måltillstånd har hittats.
- Bakåtsökning fungerar snarlikt framåtsökning, men den börjar i något av måltillstånden och söker "bakåt" till den hittar starttillståndet. Detta gör den genom att konstruera de handlingar som hade kunnat vara orsaken till det sista steget i planen, för att sedan fortsätta sökningen utifrån dem.
I både framåtsökning och bakåtsökning kan olika heuristiker användas med fördel.