(IST project IST-FET-2001-37004) |
The representation and manipulation of knowledge is one of the central tasks underlying the realization of intelligent systems.
One access to this area is the use of
declarative approaches, in which knowledge is represented as sentences in
symbolic languages and inference rules access these sentences for the process
of finding conclusions from a given set of premises.
The Answer-Set Programming approach
is characterized by the feature that problems are represented in terms of logic programs such that the models of the latter determine the solutions of the original problem:
More specifically, to encode the general features of the tackled problem, one uses a common program, i.e. a set of inference-rules with variables, abstracting a concrete instances of the problem, at hand. The instance is then fed into this program as a set of facts (like a database):
Answer-set Programming is thus in contrast to knowledge representation as done by means of formal logics, in which a proof constitutes an answer to a reasoning problem. The strength and distinguishing feature of Answer-Set Programming hereby is its advanced capability of dealing with incomplete information and defaults, basically provided by nonmonotonic negation.
Compared to similar representation approaches as SAT (satisfiability of classical propositional logic) and its extension to Quantified SAT, ASP provides the programmer with variables which allow for more compact and readable problem representations. In particular, it is easy to express concepts as transitive closure.
Compared to other logic programming formalisms such as Prolog or Constraint Logic Programming, ASP builds on models of programs rather than on proofs and query answering. ASP has built-in nondeterminism and is fully declarative, in the sense that the order of rules and subgoals in rules does not matter. This makes the language more user-friendly, in particular concerning termination issues: ASP programs always terminate (while even simple Prolog programs might not), even under arbitrary usage of negation.
Answer-Set Programming has been successfully applied to many areas including
In what follows, we provide links to some selected model applications, which are provided as demos by different WASP-nodes.
Modern software products are large and may consist of thousands of components where each component provides some specific functionality. In the configuration management problem one has to deal with various information: Given a description of the components and a set of user requirements, one has to find a valid configuration of components that satisfies the requirements. The following showcase demonstrates how ASP can be used to solve this problem. Moreover, this application provides also a diagnostic model that explains why it is not possible to satisfy a given set of user requirements.
Information integration is the task of providing a uniform interface to various pre-existing data sources, so as to enable users to focus on specifying what they want, rather than on thinking of how to obtain the answer.
Information integration is one of the core problems in distributed databases, cooperative information systems, and data warehousing, which are key areas in the software development industry, and has emerged as a crucial issue in many organizations, due to the increasing number of different information sources available both inside and outside the organization. And, obviously, inter-organization information exchange is rapidly growing as a byproduct of the expansion of the Internet and the World Wide Web.
The first demo shows a particular application of ASP within the INFOMIX-project where so-called repair programs are used to deal with potentially inconsistent information.
The second demo demonstrates that ASP is a suitable paradigm for defining and implementing query answering techniques in the so-called Global-as-View approach.
Incorporating Security Engineering into Software Requirements Engineering is an important research topic, and in particular since capturing trust and security requirements at an organizational level is a challenging problem. The following demonstration presents a CASE tool which allows the creation of formally consistent security requirements systems and performs integrity analysis according to agent-oriented requirements. The task of the overall system verification is achieved through the ASP paradigm.
Multi-agent systems have been recognized as a promising paradigm for distributed problem solving, and numerous multi-agent platforms and frameworks have been proposed, which allow to program agents in languages ranging from imperative over object-oriented to logic-based ones.
The first demo demonstrates the use of ASP for specifying and verifying socially acceptable patterns of agent interaction in multi-agent systems.
The second demo presents a monitoring application which aids in automatically detecting that agents do not collaborate properly. This showcase is implemented within a multi-agent framework IMPACT and the ASP-based planning frontend
DLV-K (see also here).
Reasoning support for the Semantic Web is currently mainly restricted to terminological reasoning in description logics and there is no broad consensus on what will constitute the logical layer of the Semantic Web. ASP can be used to support nonmonotonic formalisms and the representation of default knowledge, i.e., the mechanism of "jumping to conclusions" in the presence of incomplete or uncertain information. The showcase below provides, in particular, the coupling of ASP with OWL, which is the W3C-standard for the semantic web.
The area of planning is since its early days, one of the
challenging problems in AI. The task is simply to find a sequence
of actions leading an agent from an initial state to a desired goal
state. In contrast to classical planning, where complete
knowledge about the scenario is assumed, knowledge-based planning
deals with further, more real-world like features, as incomplete
knowledge about the domain and non-deterministic actions.
The first demo shows an approach to Hierarchical Task Network (HTN) planning using ASP.
The second showcase demonstrates some applications for the dedicated planning system