planningprobleem

Een planningprobleem is een formele taak uit de kunstmatige intelligentie waarbij een agent een opeenvolging van handelingen moet vinden die de wereld van een initiële toestand naar een doeltoestand brengt. Een succesvol plan voldoet aan de gewenste voorwaarden en laat zien hoe het systeem van begin tot doel kan opereren.

De belangrijkste onderdelen zijn: een initiële toestand I die de huidige feiten beschrijft; een doeltoestand G die bereikt moet worden; en een verzameling acties A. Elke actie heeft precondities die waar moeten zijn in de huidige toestand en effecten die de toestand veranderen, bijvoorbeeld toevoegingen (add) en verwijderen (delete) van feiten. Soms spelen ook conditionele effecten of meer complexe voorwaarden een rol.

Representaties voor planning omvatten onder andere STRIPS en het Planning Domain Definition Language (PDDL). Een planningstaak bestaat uit I, G en de acties; een plan is een volgorde van acties die, toegepast op I, resulteert in een toestand die voldoet aan G. Naast eenvoudige planlengte kunnen ook kosten en optimalisatiecriteria een rol spelen bij de keuze van het beste plan.

Algorithmisch worden plannen vaak gevonden via vooruitzoeken (progressie) of terugzoeken (regressie), ondersteund door heuristieken en concepten zoals planningsgrafen en SAT-/SMT-benaderingen. Deze methoden worden gecombineerd en aangepast aan de specificaties van het model en de eisen aan de oplossing.

Toepassingen bevinden zich in robotica, logistiek, productie en automatisering, waar het automatiseren van opeenvolgende handelingen cruciaal is. PDDL dient als de gangbare standaard om planningdomeinen en -problemen te definiëren, zodat verschillende planners vergelijkbaar en uitwisselbaar blijven.