Publication

Restarts and Nogood Recording in Qualitative Constraint-based Reasoning

Jingshi Li
2010
Conference Papers

Abstract

This paper introduces restart and nogood recording techniques in the domain of qualitative spatial and temporal reasoning. Nogoods and restarts can be applied orthogonally to usual methods for solving qualitative constraint satisfaction problems. In particular, we propose a more general definition of nogoods that allows for exploiting information about nogoods and tractable subclasses during backtracking search. First evaluations of the proposed techniques show promising results.

Official source

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Jingshi Li
2010
Conference Papers

Abstract

Official source

Related concepts (16)

Commonsense reasoning

In artificial intelligence (AI), commonsense reasoning is a human-like ability to make presumptions about the type and essence of ordinary situations humans encounter every day. These assumptions include judgments about the nature of physical objects, taxonomic properties, and peoples' intentions. A device that exhibits commonsense reasoning might be capable of drawing conclusions that are similar to humans' folk psychology (humans' innate ability to reason about people's behavior and intentions) and naive physics (humans' natural understanding of the physical world).

Symbolic artificial intelligence

In artificial intelligence, symbolic artificial intelligence is the term for the collection of all methods in artificial intelligence research that are based on high-level symbolic (human-readable) representations of problems, logic and search. Symbolic AI used tools such as logic programming, production rules, semantic nets and frames, and it developed applications such as knowledge-based systems (in particular, expert systems), symbolic mathematics, automated theorem provers, ontologies, the semantic web, and automated planning and scheduling systems.

Backtracking

Backtracking is a class of algorithms for finding solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate ("backtracks") as soon as it determines that the candidate cannot possibly be completed to a valid solution. The classic textbook example of the use of backtracking is the eight queens puzzle, that asks for all arrangements of eight chess queens on a standard chessboard so that no queen attacks any other.

Related publications (2)

Restarts and Nogood Recording in Qualitative Constraint-based Reasoning

Chat with Graph Search

Scalable maximal subgraph mining with backbone-preserving graph convolutions

A survey and comparison of contemporary algorithms for computing the matrix geometric mean