1998 | ReviewPaper | Buchkapitel
Complexity of precedence graphs for assembly and task planning
verfasst von : João Rocha, Carlos Ramos, Zita Vale
Erschienen in: Methodology and Tools in Knowledge-Based Systems
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
This paper deals with a complete and correct method to compute how many plans exist for an assembly or processing task. Planning is a NP-hard problem and then, in some situations, the application of time consuming search methods must be avoided. However, up to now the computation of the exact number of alternative plans for any situation was not reported elsewhere. Notice that the complexity of the problem does not depend on the number of involved operations, components or parts. The complexity of the problem depends on the topology of the precedences between operations. With the method presented in this paper, it will be easy to decide the search method to use, since we know how many possible plans could exist before applying the search method.