Under de senaste åren har det gjorts flera studier om den beräkningsmässiga komplexiteten i klassisk planering under förutsättning att planeraren har fullständig kunskap om den initiala situationen. På senare tid har man föreslagit att man skall använda "sensoriska" åtgärder för att planera i närvaro av ofullständighet. I detta dokument studerar vi komplexiteten i planeringen i sådana fall. I vår studie använder vi åtgärdsbeskrivningen språk A föreslås 1991 av Gelfond och Lifschitz, och dess förlängningar. Det är känt att om vi bara betraktar planer av genomförbar (polynomisk) längd, planering { med fullständig information om den ursprungliga situationen { i A är NP-fullständig: även kontrollera om ett visst mål kan uppnås från ett givet initialtillstånd är NP-fullständig. I detta dokument visar vi att planeringsproblemet i närvaro av ofullständighet verkligen är svårare: det hör till nästa nivå av komplexitetshierarki (i exakta termer är det 2 P-fullständigt). För att övervinna komplexiteten i detta problem har Baral och Son föreslagit flera approximationer. Vi visar att under vissa omständigheter, en av dessa approximationer { 0- approximation { gör problemet NP-fullbordande (vilket faktiskt minskar dess komplexitet).
Med andra ord, komplexiteten i den villkorade planering problem som presenteras i detta dokument i NPfullständig, medan komplexiteten i den villkorade planering problem för åtgärdsteorier med villkorliga effekter är 2 P -fullständig REF.
Computational Complexity of Planning and Approximate Planning in Presence of Incompleteness
{'venue': 'IJCAI', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}