BROWSE TOPICS
RESOURCESABOUT THIS SITE |
Constraint-Based ReasoningUsing Constraints for Planning, Scheduling & Design AITopics > Reasoning > Constraint-Based Reasoning
Introductory ReadingsAgents, Bodies, Constraints, Dynamics, and Evolution (2009). AI Magazine 30 (1) by Alan K. Mackworth. Downloadable PDF file. "The theme of this article is the dynamics of evolution of agents. That theme is applied to the evolution of constraint satisfaction, of agents themselves, of our models of agents, of artificial intelligence and, finally, of the Association for the Advancement of Artificial Intelligence (AAAI). The overall thesis is that constraint satisfaction is central to proactive and responsive intelligent behavior."
The Constraints Archive. Maintained at 4C (the Cork Constraint Computation Center) by Dr. Rick Wallace. On-Line Guide to Constraint Programming. By Roman Bartack. "I have opened this site as an on-line tutorial or, if you want, a textbook for beginners to the area of constraint programming. This area belongs to the less known software technologies but it rapidly evolves and brings a significant commercial interest." Constraints - An International Journal. Springer US. "Constraints provides a common forum for the many disciplines interested in constraint programming and constraint satisfaction and optimization, and the many application domains in which constraint technology is employed. It covers all aspects of computing with constraints: theory and practice, algorithms and systems, reasoning and programming, logics and languages." The Quasigroup Completion Problem. A very impressive (and colorful) demo from Carla P. Gomes.
General ReadingsDisaster Evacuation Support. By Christopher J. Carpenter, Christopher J. Dugan, Joseph B. Kopena, Robert N. Lass, Gaurav Naik, Duc N. Nguyen, Evan Sultanik, Pragnesh Jay Modi, and William C. Regli. In Proceedings of the Twenty-Second National Conference on Artificial Intelligence, 1964 - 1965. Menlo Park, Calif.: AAAI Press (2007). Abstract: "This demonstration presents an application of distributed constraint optimization and wireless networking to the task of assigning evacuees to available shelters during an emergency evacuation." Constraints and Agents: Confronting Ignorance. By Peggy S. Eaton, Eugene C. Freuder, and Richard J. Wallace. AI Magazine 19(2): Summer 1998, 51-65 "Research on constraints and agents is emerging at the intersection of the communities studying constraint computation and software agents. Constraint- based reasoning systems can be enhanced by using agents with multiple problem-solving approaches or diverse problem representations. The constraint computation paradigm can be used to model agent consultation, cooperation, and competition. An interesting theme in agent interaction, which is studied here in constraint-based terms, is confronting ignorance: the agent’s own ignorance or its ignorance of other agents." Generating and Solving Logic Puzzles through Constraint Satisfaction. By Barry O'Sullivan and John Horan. In Proceedings of the Twenty-Second National Conference on Artificial Intelligence, 1974 - 1975. Menlo Park, Calif.: AAAI Press (2007). Abstract: "Solving logic puzzles has become a very popular past-time, particularly since the Sudoku puzzle started appearing in newspapers all over the world. We have developed a puzzle generator for a modification of Sudoku, called Jidoku, in which clues are binary disequalities between cells on a 9x9 grid. Our generator guarantees that puzzles have unique solutions, have graded difficulty, and can be solved using inference alone. This demonstration provides a fun application of many standard constraint satisfaction techniques, such as problem formulation, global constraints, search and inference. It is ideal as both an education and outreach tool. Our demonstration will allow people to generate and interactively solve puzzles of user-selected difficulty, with the aid of hints if required, through a specifically built Java applet." Constraint Logic Programming - A child of Prolog finds new life solving programming's nastier problems. By Dick Pountain. Byte (February 1995). "A CLP program still needs to search a database of facts, but it can use constraints to rule out many possible outcomes and prune away large parts of the search tree." An Interactive Constraint-Based Approach to Sudoku. By Christopher Reeson, Ken Bayer, Berthe Y. Choueiry, and Kai-Chen Huang. In Proceedings of the Twenty-Second National Conference on Artificial Intelligence, 1976 - 1977. Menlo Park, Calif.: AAAI Press (2007). Abstract: "We present a Java applet, Solver, that allows a user to interactively solve a Sudoku problem using Constraint Processing (CP) techniques. We also present a companion Java applet, Constructor, that allows human users to enter and store new puzzle instances. Our system showcases the power of CP techniques in solving problems through a widely familiar and easily approachable puzzle. Our Solver is built to maximize the interactions between the human users and CP techniques. It allows the users to apply different consistency algorithms, work specifically on certain constraints, and make assignments and domain reductions on their own. We also designed a hint functionality that uses Solving Crossword Puzzles as Probabilistic Constraint Satisfaction. By Noam M. Shazeer, Michael L. Littman, and Greg A. Keim, Duke University. 1999. In Proceedings of the Sixteenth National Conference on Artificial Intelligence, 156 - . Menlo Park, Calif.: AAAI Press. "Crossword puzzle solving is a classic constraint satisfaction problem, but, when solving a real puzzle, the mapping from clues to variable domains is not perfectly crisp. At best, clues induce a probability distribution over viable targets, which must somehow be respected along with the constraints of the puzzle. Motivated by this type of problem, we provide a formal model of constraint satisfaction with probabilistic preferences on variable values. Two natural optimization problems are defined for this model: maximizing the probability of a correct solution, and maximizing the number of correct words (variable values) in the solution. We provide an efficient iterative approximation for the latter based on dynamic programming and present very encouraging results on a collection of real and artificial crossword puzzles." Related Resources"The Computational Intelligence Research Laboratory (CIRL) of the University of Oregon has a research focus on basic questions in artificial intelligence including search, knowledge representation, and reasoning. Emphasis is on planning, constraint satisfaction, and commonsense reasoning." Constraint Solving and Programming techniques, a collection of resources from the Constraints Research and Reading Group (CR2G), at the University of Texas at El Paso. #4cThe Cork Constraint Computation Centre (4C). "Difficult problems can offer too many choices, many of which are incompatible, few of which are optimal. The Cork Constraint Computation Centre develops the basic science that will make it easier for computers to help us make these choices."
Fraunhofer FIRST Institute for Computer Architecture and Software Technology. Projects include:
Related AITopics Pages |
