NDLI: Conditional and composite temporal CSPs

Content Provider	Springer Nature Link
Author	Mouhoub, Malek Sukpan, Amrudee
Copyright Year	2010
Abstract	Constraint Satisfaction Problems (CSPs) have been widely used to solve combinatorial problems. In order to deal with dynamic CSPs where the information regarding any possible change is known a priori and can thus be enumerated beforehand, conditional constraints and composite variables have been studied in the past decade. Indeed, these two concepts allow the addition of variables and their related constraints in a dynamic manner during the resolution process. More precisely, a conditional constraint restricts the participation of a variable in a feasible scenario while a composite variable allows us to express a disjunction of variables where only one will be added to the problem to solve. In order to deal with a wide variety of real life applications under temporal constraints, we present in this paper a unique temporal CSP framework including numeric and symbolic temporal information, conditional constraints and composite variables. We call this model, a Conditional and Composite Temporal CSP (or CCTCSP). To solve the CCTCSP we propose two methods respectively based on Stochastic Local Search (SLS) and constraint propagation. In order to assess the efficiency in time of the solving methods we propose, experimental tests have been conducted on randomly generated CCTCSPs. The results demonstrate the superiority of a variant of the Maintaining Arc Consistency (MAC) technique (that we call MAX+) over the other constraint propagation strategies, Forward Checking (FC) and its variants, for both consistent and inconsistent problems. It has also been shown that, in the case of consistent problems, MAC+ outperforms the SLS method Min Conflict Random Walk (MCRW) for highly constrained CCTCSPs while both methods have comparable time performance for under and middle constrained problems. MCRW is, however, the method of choice for highly constrained CCTCSPs if we decide to trade search time for the quality of the solution returned (number of solved constraints).
Starting Page	90
Ending Page	107
Page Count	18
File Format	PDF
ISSN	0924669X
Journal	Applied Intelligence
Volume Number	36
Issue Number	1
e-ISSN	15737497
Language	English
Publisher	Springer US
Publisher Date	2010-07-30
Publisher Place	Boston
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Temporal Reasoning Constraint Satisfaction Stochastic Local Search Mechanical Engineering Artificial Intelligence (incl. Robotics) Manufacturing, Machines, Tools
Content Type	Text
Resource Type	Article
Subject	Artificial Intelligence

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Managing dynamic CSPs with preferences

Dynamic Flexible Constraint Satisfaction

Visual analogy: Viewing analogical retrieval and mapping as constraint satisfaction problems

Boosting MUC extraction in unsatisfiable constraint networks

Querying Temporal Constraint Networks: A Unifying Approach

A Connectionist Approach for Solving Large Constraint Satisfaction Problems

Conversational Case-Based Reasoning

Action-Based Causal Reasoning

Massively Parallel Probabilistic Reasoning with Boltzmann Machines

Conditional and composite temporal CSPs

Similar Documents

Managing dynamic CSPs with preferences

Dynamic Flexible Constraint Satisfaction

Visual analogy: Viewing analogical retrieval and mapping as constraint satisfaction problems

Boosting MUC extraction in unsatisfiable constraint networks

Querying Temporal Constraint Networks: A Unifying Approach

A Connectionist Approach for Solving Large Constraint Satisfaction Problems

Conversational Case-Based Reasoning

Action-Based Causal Reasoning

Massively Parallel Probabilistic Reasoning with Boltzmann Machines

Conditional and composite temporal CSPs