A geometric approach to anytime constraint solving for TCSPs
Journal
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Journal Volume
1531
Pages
365-376
Date Issued
1998
Author(s)
Abstract
Temporal constraint satisfaction problems (TCSPs) are typically modelled as graphs or networks. Efficient algorithms are only available to find solutions for problems with limited topology. In this paper, we propose constraint geometry as an alternative approach to modeling TCSPs. Finding solutions to a TCSP is transformed into a search problem in the corresponding n-dimensional space. Violations of constriants can be measured in terms of spatial distances. As a result, approximate solutions can be identified when it is impossible or impractical to find exact solutions. A real-numbered evolutionary algorithm with special mutation operators has been designed to solve the general class of TCSPs. It can render approximate solutions at any time and improve the solution quality if given more time. Experiments on hundreds of randomly generated problems with representative parameters showed that the algorithm is more efficient and robust in comparison with the pathconsistency algorithm. © Springer-Verlag Berlin Heidelberg 1998.
Other Subjects
Algorithms; Artificial intelligence; Evolutionary algorithms; Approximate solution; Constraint Solving; Finding solutions; Geometric approaches; Mutation operators; N-dimensional space; Path consistency; Temporal constraint satisfaction problems; Constraint satisfaction problems
Type
conference paper
File(s)![Thumbnail Image]()
Loading...
Name
04.pdf
Size
634.1 KB
Format
Adobe PDF
Checksum
(MD5):5ff8246dfc7311cbd3f627413958a084