|
| << vorige |
Tijdschrift beschrijving
Alle jaargangen van het bijbehorende tijdschrift
Alle afleveringen van het bijbehorende jaargang
Alle artikelen van de bijbehorende aflevering
Details van artikel 6 van 6 gevonden artikelen
| Titel: |
Underconstrained knowledge-intensive constraint satisfaction search |
| Auteur: |
Hofmann, Martin O. |
| Verschenen in: |
Journal of experimental & theoretical artificial intelligence |
| Paginering: | Jaargang 7 (1995) nr. 2 pagina's 195-215 |
| Jaar: |
1995-04-01 |
| Inhoud: |
This paper describes a methodology to efficiently solve underconstrained knowledge-intensive constraint satisfaction problems (CSPs) where solutions are ordered by a cost measure. The methodology exploits a segmentation of the CSP imposed by the application domain. Constraints and variables are clustered into CSP segments which support local constraint processing and solution cost estimation. The methodology employs heuristic search to develop solutions in an incremental fashion. The goal of search is to find one or several of a set of 'satisficing', i.e. good enough, solutions. Solution cost is defined as distance to a normal solution. The heuristic evaluation function is non-admissible and favours depth-first search because finding a good solution is more important than finding the absolute best one. The value of the evaluation function of a search node may change during processing in response to results of exploring nearby nodes. It attempts to improve its estimate of the remaining path cost based on regularities of the search space. The presented methodology thus has the potential of expanding fewer nodes than A*. The intended application is model-based device diagnosis. We develop limits on the deterioration of solution quality due to the non-admissible evaluation function and give some experimental results from the primary application. |
| Uitgever: |
Taylor & Francis |
| Bronbestand: |
Elektronische Wetenschappelijke Tijdschriften |
Details van artikel 6 van 6 gevonden artikelen
| << vorige |