A Prolog technique of implementing search of A/O graphs with constraints

Authors: M. Bieliková and P. Návrat

Reference: Journal Computers and Artificial Intelligence, 16(4):377-400, 1997.

Contents:

1. Problem area and goal
2. Related Work
3. The basic algorithm for (chronological) backtracking
4. The enhanced algorithm
• Handling the case of an impossible node
• Handling the case of a conflicting node
• Applying the technique of node marking
5. Application in building a software configuration
6. Experiments
• Method of Experimentation
• Results of the Experiments
7. Conclusion

Abstract: Our research has been motivated by the task of forming a solution subgraph which satisfies given constraints. The problem is represented by an A/O graph. Our approach is to apply a suitably modified technique of dependency-directed backtracking. We present our formulation of the standard chronological backtracking algorithm in Prolog. Based on it, we have developed an enhanced algorithm which makes use of special heuristic knowledge. It involves also the technique of node marking. We have gathered experience with the prototype Prolog implementation of the algorithm in applying it to (one step of) the problem of building a software configuration. Our experience shows that Prolog programming techniques offer a considerable flexibility in implementing the above outlined tasks.

Keywords: A/O-graph, non-chronological backtrack, Prolog

PS version (178K file, 23 pages) together with a GZ version (64K file) is available.

to Homepage

to Publications

to the Top