Modeling and solving constraint satisfaction problems through petri nets

Risultato della ricerca: Capitolo in libro/report/atti di convegnoContributo a conferenzapeer review

Abstract

Constraint satisfaction problems (CSP) represent one of the most studied areas in Artificial Intelligence and related disciplines. A lot of theoretical problems and applications, including computer vision, job-shop scheduling, planning, design and others, can be formulated as problems r~lated to the satisfaction of constraints. Classical approaches to the solution of CSP are usually based on some form of backtracking search; such approaches suffer, in the general case, of some drawbacks essentially represented by the so-called thrashing behavior, a problem arising when the search algorithm repeatedly explores parts of the search space not leading to any solution. In this paper an alternative approach to backtracking search is proposed by modeling a system of constraints through an ordinary Petri net model. The Petri net model is able to capture every finite domain CSP, representing a wide and significant class of CSP used in applications. Algebraic analysis is then exploited for solving the CSP corresponding to the net model. In particular, even if a direct application of the fundamental equation of Petri nets would be theoretically possible, such a possibility could be unsatisfactory in practice. Because of that, a cyclic net model for CSP is introduced, such that the whole set of solutions can be characterized by means of a subset of the set of minimal support T-invariants of the net model. An algorithm able to directly compute only such a subset of invariants is then proposed as the core process for solving a CSP.

Lingua originaleInglese
Titolo della pubblicazione ospiteApplication and Theory of Petri Nets 1997 - 18th International Conference, ICATPN 1997, Proceedings
EditorGianfranco Balbo, Pierre Azema
EditoreSpringer Verlag
Pagine348-366
Numero di pagine19
ISBN (stampa)3540631399, 9783540631392
DOI
Stato di pubblicazionePubblicato - 1997
Pubblicato esternamente
Evento18th International Conference on Application and Theory of Petri Nets, ICATPN 1997 - Toulouse, France
Durata: 23 giu 199727 giu 1997

Serie di pubblicazioni

NomeLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume1248
ISSN (stampa)0302-9743
ISSN (elettronico)1611-3349

???event.eventtypes.event.conference???

???event.eventtypes.event.conference???18th International Conference on Application and Theory of Petri Nets, ICATPN 1997
Paese/TerritorioFrance
CittàToulouse
Periodo23/06/9727/06/97

Fingerprint

Entra nei temi di ricerca di 'Modeling and solving constraint satisfaction problems through petri nets'. Insieme formano una fingerprint unica.

Cita questo