FUZZY CONSTRAINTS

• “From Crisp to Fuzzy Constraint Networks”,
  M. Giacomin
  CP '01 Workshop “Modelling and Solving Problems with Soft Constraints”, Paphos, Cyprus, December 2001
  
  Several instances of the CSP framework have been proposed to handle specific problems, such as temporal and spatial reasoning formalisms. This paper, standing at a high level of abstraction, studies the problem of extending these specific instances in order to handle fuzzy constraints. The concepts of class of networks, property, algorithm and the relevant fuzzy extensions are defined. Some application examples in the field of temporal reasoning are provided.
  [PDF]
  
   

QUALITATIVE FUZZY TEMPORAL REASONING

• “Tractable Fragments of Fuzzy Qualitative Algebra”,
  S. Badaloni, M. Falda, M. Giacomin
  Spatial Cognition and Computation, vol. 8(1-2), 150-166, Taylor and Francis, 2008.
     
  In this paper we study the computational complexity of Fuzzy Qualitative Temporal Algebra (QA^fuz), a framework that combines qualitative temporal constraints between points and intervals, and allows modelling vagueness and uncertainty. Its tractable fragments can be identified by generalizing the results obtained for crisp Constraint Satisfaction Problems (CSPs) to fuzzy CSPs (FCSPs); to do this, we apply a general methodology based on the notion of a-cut. In particular, the results concerning the tractability of Qualitative Algebra QA, obtained in a recent study by different authors, can be extended to identify the tractable algebras of the fuzzy Qualitative Algebra QA^fuz in such a way that the obtained set is maximal, namely any maximal tractable fuzzy algebra belongs to this set.
  © Taylor and Francis
    
    

• “Solving temporal over-constrained problems using fuzzy techniques”,
  S. Badaloni, M. Falda, M. Giacomin
  Journal of Intelligent and Fuzzy Systems, vol. 18(3), 255-265, IOS Press, 2007.
    
  The satellite-scheduling problem represents an interesting field to test non-conventional temporal solvers because scheduling-problems are inherently over-constrained and, moreover, the tasks may be known in an imprecise and uncertain manner. In this paper we present an application of our fuzzy temporal reasoning system to the satellite-scheduling problem. First, we describe our model of integration of qualitative and quantitative temporal information affected by vagueness and uncertainty. Then, we show the usefulness of fuzzy constraints when dealing with over-constrained temporal problems.
  © IOS Press
   
   

• “Fuzzy Extensions of Qualitative Algebra Tractable Fragments”, 
  S. Badaloni, M. Falda, M. Giacomin, 
  Proc. of IJCAI-07 Workshop on Spatial and Temporal Reasoning, 11-15, Hyderabad, India, January 2007.
    
  In this paper we address the problem of finding tractable fragments of the Fuzzy Qualitative Temporal Algebra QA^fuz, an integrated framework able to deal with qualitative temporal constraints between points and intervals affected by vagueness and uncertainty. To this aim, we apply a general methodology based on the notion of a-cut that allows us to generalize the results obtained for crisp Constraint Satisfaction Problem (CSP) to fuzzy CSP (FCSP). In particular, the results concerning the tractability of Qualitative Algebra QA, obtained in a recent study by different authors, can be extended to identify the tractable fragments of the fuzzy Qualitative Algebra QA^fuz. In order to guarantee the applicability of Path-Consistency algorithm, we prove that the identified fragments are algebras.
    
    

• “The algebra IA^fuz: a framework for qualitative fuzzy temporal reasoning”,
  S. Badaloni, M. Giacomin
  Artificial Intelligence, vol. 170 (10), 872-908, Elsevier Science, 2006.
    
  The aim of this work is to integrate the ideas of flexibility and uncertainty into Allen's interval-based temporal framework, defining a new formalism, called IA^fuz, which extends classical Interval Algebra (IA), in that qualitative fuzzy constraints can be expressed between intervals. We generalize the classical operations between IA-relations to IA^fuz-relations, as well as the concepts of minimality and local consistency, referring to the framework of Fuzzy Constraint Satisfaction Problem. We analyze the most interesting reasoning tasks in our framework, which generalize the classical problems of checking consistency, finding a solution, and computing the minimal network in the context of IA. In order to solve these tasks, we devise two constraint propagation algorithms and a Branch & Bound algorithm. Since these tasks are NP-complete, we address the problem of finding tractable sub-algebras of IA^fuz, by extending to our fuzzy framework the classical pointizable sub-algebras SAc and SA, as well as the maximal tractable subalgebra H introduced by Nebel. In particular, we prove that the fuzzy extension of the latter, called H^fuz, shares with its classical counterpart a maximality property, in that it is the unique maximal subalgebra of IA^fuz which contains the fuzzy extensions of Allen's atomic relations.
  © Elsevier Science
   
   

• “Fuzzy extension of interval-based temporal sub-algebras”,
  S. Badaloni, M. Giacomin
  Proc. of 9th Information Processing and Management of Uncertainty in Knowledge-Based System Conference (IPMU 2002), 1119-1126, Annecy, France, July 2002.
  
  In a previous paper, we have proposed a fuzzy extension of Allen's Interval Algebra, called IA^fuz, which is able to model soft temporal constraints and uncertainty in a unified way. In this paper, we address the problem of finding tractable sub-algebras of IA^fuz, as it has been done in the classical case. In particular, we show that the fuzzy extensions of classical SAc and SA sub-algebras are tractable sub-algebras of IA^fuz.
  [PDF]
   
   

• “Flexible temporal constraints”,
  S. Badaloni, M. Giacomin
  Proc. of 8th Information Processing and Management of Uncertainty in Knowledge-Based System Conference (IPMU 2000), 1262-1269, Madrid, Spain, July 2000.
  
  This paper proposes a fuzzy temporal reasoner based on an interval constraint network. It includes two types of flexible constraints: soft constraints to express preferences among feasible solutions, and prioritized constraints to express the degree of necessity of their satisfaction. A fuzzy interval algebra IA^fuz is defined as a generalization of the classical one. To deal with scheduling in this framework, a simple decision problem in an office environment is shown.
  [PDF]
  
   

• “A fuzzy extension of Allen’s Interval Algebra”,
  S. Badaloni, M. Giacomin
  E. Lamma, P. Mello (Eds.), AI*IA99: Advances in Artificial Intelligence, Selected Papers - Lecture Notes in Artificial Intelligence 1792, 155-165, Springer-Verlag, 2000.
  
  The aim of this work is to integrate the ideas of flexibility and uncertainty into Allen's interval-based temporal logic, defining a new formalism which extends classical Interval Algebra (IA). Some results obtained in the framework of Fuzzy Constraint Satisfaction Problem (FCSP) approach are used in the specific domain of temporal reasoning. A new fuzzy interval algebra IA^fuz is defined. Classical concepts of consistency and minimality are generalized to deal with IA^fuz. Path-consistency and branch & bound algorithms are shown. A tractable sub-algebra of IA^fuz is defined.
  © Springer-Verlag - LNAI 1792  [PDF]
  
   

• “A fuzzy extension of interval-based constraint networks”,
  S. Badaloni, M. Giacomin
  Proc. of Workshop on Integration of AI and OR techniques in Constraint Programming for Combinatorial Optimization Problems (CP-AI-OR-99), 52-56, Ferrara, Italy, February 1999.

  The aim of this work is to integrate the ideas of flexibility and uncertainty into Allen's interval-based temporal logic, defining a new formalism (IA^fuz ) which extends classical Interval Algebra (IA). We refer to Dubois, Fargier & Prade approach to Fuzzy Constraint Satisfaction Problem (FCSP), in which constraints are satisfied to a degree; this framework is based on Fuzzy Sets and Possibility Theory, which is a more robust approach to uncertainty with respect to probabilistic one. While FCSP has been applied in job-shop scheduling problems to deal with quantitative temporal information (such as job release date and due date), in the present work we deal exclusively with the qualitative aspect of temporal knowledge since it may be convenient for the solution of planning problems. A new fuzzy interval algebra IA^fuz is defined. Classical concepts of consistency and minimality are generalized to deal withIA^fuz networks. Path-consistency and branch & bound algorithms are shown.
  [PDF]

HYBRID FUZZY TEMPORAL REASONING
 

• “Integrating Quantitative and Qualitative Fuzzy Temporal Constraints”,
  S. Badaloni, M. Falda, M. Giacomin
  AI Communications, vol. 17 (4), 187-200, IOS Press, 2004.
    
  In this work we address the problem of representing and reasoning with temporal knowledge in a very general and flexible manner. To this aim we propose a model of integration of quantitative and qualitative temporal information affected by vagueness and uncertainty. We extend our fuzzy qualitative temporal framework IAfuz integrating the treatment of fuzzy quantitative constraints modeled as trapezoidal distributions. To do this, we extend the treatment of fuzzy temporal constraints considered in the literature and we generalize in a fuzzy direction the classical hybrid approach of temporal constraints integration proposed by Meiri. To show the full expressiveness of the new system, we apply it to represent the fuzzy temporal knowledge in a typical scheduling example.
    
    

• “An Hybrid Fuzzy Temporal Constraint Approach: a Case Study”,
  S. Badaloni, M. Falda, M. Giacomin
  Proc. of 10th Information Processing and Management of Uncertainty in Knowledge-Based System Conference (IPMU 2004), 1585-1592, Perugia, Italy, July 2004.
  
  In this paper, we propose an application of an integrated model for temporal reasoning able to handle both quantitative and qualitative constraints affected by vagueness and uncertainty. The integration is obtained by merging two existing models, i.e. Meiri's system, that handles qualitative and quantitative classical temporal constraints, and our IA^fuz, that handles fuzzy qualitative constraints. The first approach is generalized with possibility theory, while the second is extended to include quantitative constraints. We present a practical application of our framework in a simplified problem of investigation.
  
   

• “Integrating Qualitative and Quantitative Constraints in Fuzzy Temporal Networks”,
  S. Badaloni, M. Falda, M. Giacomin
  R. Rodriguez (Editor), Proc. of IJCAI-03 Workshop on Spatial and Temporal Reasoning, 105-112, Acapulco, Mexico, August 2003.
  
  In this preliminary work, we study an integrated framework able to handle both quantitative and qualitative constraints affected by vagueness and uncertainty. We merge two existing models: the Meiri's system, that handles qualitative and quantitative classical temporal constraints, and our IA^fuz, that handles fuzzy qualitative constraints. The first approach is generalized with possibility theory, while the second is extended in order to include quantitative constraints. We consider two traditional solving techniques, namely Path-Consistency and Branch & Bound, in order to make network constraints more explicit and to find an optimal solution, respectively. A simple scheduling example shows the main features of the new system.
  
   

• “Qualitative and Quantitative Fuzzy Temporal Constraints”,
  S. Badaloni, M. Falda, M. Giacomin
  Atti dell’Ottavo Convegno dell’Associazione Italiana per l’Intelligenza Artificiale, 39, Siena, Italy, Settembre 2002.
  
  This paper describes a model for temporal reasoning that handles both quantitative and qualitative information affected by vagueness and uncertainty. Starting from two existing models, namely the Meiri's system and IA^fuz, the proposed approach generalizes the first to a fuzzy framework and extends the second in order to handle qualitative constraints. The system uses the Fuzzy Constraint Satisfaction Problem theory to formulate reasoning tasks and so it takes advantage of traditional solving techniques such as Path-Consistency and Branch and Bound. A simple scheduling example shows the main features of the new system.

(CRISP) TEMPORAL REASONING

• “Qualitative temporal representation and reasoning about points, intervals and durations”,
  S. Badaloni, M. Giacomin, C. Masolo
  C. Bettini, A. Montanari (Eds.), Proc. of 8th International Symposium on Temporal Representation and Reasoning (TIME-01), IEEE Press, 51-56, Cividale del Friuli, Italy, June 2001.
  
  Recently, an elegant framework called INDU has been proposed for representing qualitative information about time intervals and durations. INDU is a single network, therefore it avoids typical problems of bi-networks, and in addition it has interesting computational properties.  In this paper, we extend INDU in two directions: we enrich its expressive power introducing points and maintaining the same computational properties, and we provide it with an axiomatic theory able to handle qualitative temporal information about points, intervals and durations in a unified framework. This theory is based on general interval entities and two relations: general meets and not longer than.