A Constraint Decomposition Method for Spatio-Temporal Configuration Problems

Toshikazu Tanimoto

This paper describes a flexible framework and an efficient algorithm for constraint-based spatio-temporal configuration problems. Binary constraints between spatio-temporal objects are first converted to constraint regions, which are then decomposed into hierarchical data structures; based on this constraint decomposition, an improved backtracking algorithm called HBT can compute a solution quite efficiently. In contrast to other approaches, the proposed method is characterized by the efficient handling of arbitrarily-shaped objects, and the flexible integration of quantitative and qualitative constraints; it allows a wide range of objects and constraints to be utilized for specifying a spatio-temporal configuration. The method is intended primarily for configuration problems in user interfaces, but can effectively be applied to similar problems in other areas as well.


This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.