Premium
Planning in polynomial time: the SAS‐PUBS class
Author(s) -
BÄCKSTRÖM CHRISTER,
KLEIN INGER
Publication year - 1991
Publication title -
computational intelligence
Language(s) - French
Resource type - Journals
SCImago Journal Rank - 0.353
H-Index - 52
eISSN - 1467-8640
pISSN - 0824-7935
DOI - 10.1111/j.1467-8640.1991.tb00393.x
Subject(s) - computer science , time complexity , plan (archaeology) , class (philosophy) , algorithm , mathematics , artificial intelligence , humanities , combinatorics , philosophy , geography , archaeology
This article describes a polynomial‐time, O ( n 3 ), planning algorithm for a limited class of planning problems. Compared to previous work on complexity of algorithms for knowledge‐based or logic‐based planning, our algorithm achieves computational tractability, but at the expense of only applying to a significantly more limited class of problems. Our algorithm is proven correct, and it always returns a parallel minimal plan if there is a plan at all. Cet article décrit un algorithme de planification de temps polynomial O ( n 3 ) pour une classe restreinte de problemes de planification. Contrairement aux travaux précédents sur la complexité des algorithmes pour la planification basée sur la logique ou les connaissances, l' algorithme dont il est question dans cet article permet d' obtenir la tractabilityé computationnelle; cependant, il ne peut ětre appliqué qu'à une catégorie beaucoup plus restreinte de problèmes. Cet algorithme s'est done révélé correct et il génère toujours un plan minimal en parallèle lorsqu'il y en a un.