TOOLBOXBROWSE TOPICS
RESOURCESABOUT THIS SITEpmwiki.org |
Constraint-Based Reasoning(a subtopic of Reasoning)
Good Places to StartConstraint Solving. An AI Bite by Simon Colton. Sponsored by, and available from, The Society for the Study of Artificial Intelligence and Simulation of Behaviour. Artificial intelligence - Solving problems for the real world. By Billy Defrain. Daily Nebraskan (March 21, 2005). "For a typical American, the mention of artificial intelligence may conjure up nasty images of a robot wielding a plasma rifle atop a pyramid of human skulls. Mention artificial intelligence to Berthe Choueiry, though, and she thinks of problems. Choueiry, an associate professor of computer science and engineering, conducts artificial intelligence research at the University of Nebraska-Lincoln. And out of the wide field of artificial intelligence, her research focuses on constraint processing. This involves developing techniques to solve decision problems and applying them to real world uses, Choueiry said. ... She works to generate 'solutions that hopefully apply to real world problems like resource allocation, airline times and natural language processing,' Choueiry said. Although her tools are elaborate mathematical functions, her goal is to keep them as simple as possible. 'We’d like to develop tools for you to use constraints without even thinking of them or having to learn what they are,' she said. Constraint propagation, which is Choueiry’s speciality, is just one method of reasoning for artificial intelligence. Constraint-based reasoning is a deductive process in which the program looks at a group of data by considering which responses are not acceptable. These unacceptable responses are constraints.... Choueiry said one of the most difficult aspects of constraint processing is the concept of combinatorial explosion."
Constraint Satisfaction Problems: Definition of CSP - A simple example: the crossword puzzle. From Marc Torrens. Follow the links to find out what crossword puzzles have to do with CSP's. The Constraints Archive. Maintained at 4C (the Cork Constraint Computation Center) by Dr. Rick Wallace. Resources include: 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.
Readings OnlineDisaster 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." CSP & Games from Professors Tomás Lozano-Pérez & Leslie Kaelbling's Spring 2003 course, Artificial Intelligence. Available from MIT OpenCourseWare. 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 Web Sites"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 AI Topics Pages |
