Combining answer set programming with description logics for the
Semantic Web
Thomas Eiter, Giovambattista Ianni, Thomas Lukasiewicz, Roman
Schindlauer, Hans Tompits: Artificial Intelligence
172(12-13): 1495-1539 (2008)
This paper proposes dl-programs, a formalism that integrates
description logics with rule-based logic programs under answer set
semantics. It provides not only detailed theoretical analyses of
these programs in terms of their expressive power and
computational complexities, but also an implementation that
illustrates the usefulness of the proposed formalism
in the semantic web. This work highlights many difficult issues in
the problem of adding rules and default rules into description
logics, and has been very influential in subsequent work in this
area.
The CLASSIC PAPER AWARD was given to the following two papers:
STRIPS: A New Approach to the Application of Theorem Proving to
Problem Solving
Richard Fikes, Nils J. Nilsson
Artificial Intelligence 2(3/4): 189-208 (1971)
This paper lays the foundations and initial algorithms for what
has become to be known as classical planning in AI where an
agent has to perform deterministic actions for transforming a
given initial state into a goal state from a declarative and
compact representation of the actions. For this, the paper
combines ideas from logic and problem solving in the formulation
of a domain-independent problem solver where the states are
characterized by first-order logical formulas, and operators
are characterized by three sets of formulas -- the
precondition, add, and delete lists. The representation
provides a practical solution to the frame problem, which
with some variations, is still in use in current classical
and non-classical planners alike. The basic STRIPS planning
algorithm provides in turn the basis for linear and
non-linear planning algorithms, and for the view of
domain-independent classical planning as a path-finding problem in
the graph of states.
Consistency in Networks of Relations
Alan K. Mackworth
Artificial Intelligence 8(1):99-118 (1977)
This seminal paper in the field of AI devoted to solving
constraint satisfaction problems (CSPs), contains three
foundational contributions. First, the paper contributes a
fundamental insight for improving the performance of backtracking
algorithms on CSPs by identifying that local inconsistencies can
lead to much thrashing or unproductive search. Second, the paper
presents
clear definitions of conditions that characterize the level of
local consistency of a CSP, notably including the concept of arc
consistency, and precise algorithms for enforcing these levels of
local consistency by removing inconsistencies.
Such algorithms have come to be known as constraint propagation
algorithms. Third, the paper advocates the use of constraint
propagation at each node in the search tree, a technique that is
now the foundation of all open source and commercial constraint
programming systems. The paper has been immensely
influential in establishing, and guiding the research agenda of,
the field of constraint programming.
2012:
A call was only made for the Prominent Paper award. The Prominent Paper award was given to:
Learning and inferring transportation routines
Lin Liao, Donald J. Patterson,
Dieter Fox, and Henry Kautz
Vol 171 (5-6), April 2007, Pages 311-331
This paper introduces a hierarchical Markov model that can learn and infer a user's daily movements through an urban community, and applies it in an application that helps cognitively-impaired people use public transportation safely. The paper takes a realistic and important problem, and solves it by developing technically sophisticated, state-of-the-art AI techniques, that have applicability well beyond the domain described in the paper. This work has had a significant impact on the area of modeling and learning with dynamic Bayesian networks, both in and outside of AI. As such, the award committee unanimously believes the paper is a worthy winner of the inaugural AIJ Prominent Paper Award.