AIJ Awards: List of Current and Previous Winners
The 2023 Classic and Prominent Paper Awards were given to the following papers:
2023 AIJ Prominent Paper Award
Nasari: Integrating explicit knowledge and corpus statistics for a multilingual representation of concepts and entities
José Camacho-Collados, Mohammad Taher Pilehvar, Roberto Navigli
Artificial Intelligence 240:36-64 (2016)
The award is made for outstanding contributions to the multilingual representation of meanings in the form of lexical and semantic, latent and explicit vectors. This work not only achieved state-of-the-art performance for multilingual semantic similarity at the time it was published, but it also enabled Word Sense Disambiguation and Entity Linking in multiple languages (including low resource languages). This work further inspired practical application to detect lexical errors in Machine Translation that has been cited and used by industry.
2023 AIJ Classic Paper Award
Deep Blue
Murray Campbell, A.Joseph Hoane Jr., Feng-hsiung Hsu
Artificial Intelligence 134(1–2):57-83 (2002)
Over a quarter century after Deep Blue defeated Gary Kasparov in a six-game match in 1997, Deep Blue remains a milestone achievement in the progress of Artificial Intelligence. Deep Blue provided technical advances in custom hardware for advanced search algorithms and remains both a landmark in performance and a marvel of engineering achievement. Deep Blue also helped set the stage and inspire researchers to aim for further AI grand challenges in games, perhaps most notably, the game of Go.
Past AIJ Prominent and Classic Award Winning Papers
2022:
2022 PROMINENT PAPER AWARD was given to:
Optimal social choice functions: A utilitarian view
Craig Boutilier, Ioannis Caragiannis, Simi Haber, Tyler Lu, Ariel Procaccia, Or Sheffet
Artificial Intelligence 227:190-213 (2015)
This paper has made outstanding contributions to computational social choice by introducing a fundamentally novel approach to voting, now referred to as implicit utilitarian voting. It also initiated the prolific line of research on distortion, leading to survey and tutorial coverage of the topic as well as inclusion in graduate course material. Among its many contributions, the paper includes breakthrough results such as polynomial-time computability of the optimal randomized voting rule and a near-tight analysis of its distortion. It also provides an average-case analysis and learning-theoretic results, thus opening doors to a multi-faceted treatment of the subject.
2022 CLASSIC PAPER AWARD was given to:
An optimal coarse-grained arc consistency algorithm
Christian Bessiere, Jean-Charles Régin, Roland Yap, Yuanlin Zhang
Artificial Intelligence 165(2):165-185 (2005)
Constraint propagation algorithms are at the heart of the success of constraint programming, and most important of all such algorithms is that for enforcing arc consistency. This paper provided an optimal algorithm for enforcing arc consistency on generic constraints, providing an elegant proof of correctness and analysis of its complexity. The hallmarks of this work are its elegance, simplicity, efficiency and impact. This algorithm is now at the heart of most commercial and open source solvers.
2021:
2021 PROMINENT PAPER AWARD was shared by the following two papers:
Efficient Crowdsourcing of Unknown Experts using Bounded Multi-Armed Bandits
Long Tran-Thanh, Sebastian Stein, Alex Rogers, Nicholas R. Jennings
Artificial Intelligence 214:89-111 (2014)
This paper developed the first comprehensive framework for the rigorous and principled mathematical analysis of task allocation algorithms in crowdsourcing systems. It also proposed a new sequential decision making model, called bounded bandits with provable performance guarantees. Both of these contributions have had a significant impact on subsequent work by other researchers in both industry and academia in the years since its first publication.
Algorithm Runtime Prediction: Methods & Evaluation
Frank Hutter, Lin Xu, Holger Hoos, Kevin Leyton-Brown
Artificial Intelligence 206:79-111 (2014)
This paper represents a significant milestone in the field of algorithmic runtime prediction. It provides a unifying technical overview, novel technical contributions involving improvements and extensions of existing methods, and a comprehensive empirical analysis of algorithm run-time prediction across three fundamental problems in AI and Algorithms: propositional satisfiability, travelling salesperson, and mixed integer programming. This paper not only serves as an important and highly cited reference on algorithmic runtime prediction for the fields of AI and Algorithms, but it has also influenced work in High Performance and Distributed Computing as evidenced by a diverse array of citations from those fields.
2021 CLASSIC PAPER AWARD was given to:
Planning and Acting in Partially Observable Stochastic Domains
Leslie Pack Kaelbling, Michael Littman, Anthony Cassandra
Artificial Intelligence 101(1-2):99-134
This is arguably the most well-known paper for introducing the Partially Observable Markov Decision Process (POMDP) from the field of Operations Research to the field of AI. It summarized the theoretical formalism of POMDPs (as well as novel algorithmic contributions) from the lens of an AI research perspective and did so in a highly accessible and intuitive manner that demystified the technicalities of POMDPs for generations of AI researchers. The introduction and popularization of the POMDP in the field of AI not only contributed to the formal modern perspective of sequential decision-making in AI, but it also had a significant impact on the robotics community, which has adopted the POMDP as a fundamental representational formalism.
2020:
2020 PROMINENT PAPER AWARD was given to:
Conflict-Based Search for Optimal Multi-Agent Pathfinding
Guni Sharon, Roni Stern, Ariel Felner, Nathan R. Sturtevant
Artificial intelligence 219:40-66 (2015)
This paper introduced an elegant and novel formalisation of the multi-agent pathfinding problem, based on the resolution of conflicts and on searching a conflict tree. Upon its publication, this work substantially improved state-of-the art performance. In the years since, the paper has become a reference in the area, with many subsequent variations, extensions and generalisations. Today, these contributions are being successfully applied to solving a broad range of important industrial applications including aircraft towing, automated warehouses, office robots and video games.
2020 CLASSIC PAPER AWARD was given to:
Temporal Constraint Networks
Rina Dechter, Itai Meiri, Judea Pearl
Artificial intelligence 49 (1-3):61-95 (1991)
This seminal paper introduced the temporal constraint satisfaction problem (TCSP), for quantitative temporal reasoning. The TCSP, and the polytime solvable special case of simple (non-disjunctive) temporal problems, have gained widespread use in planning & scheduling and other applications. The simple and elegant problem formulation of this paper also inspired subsequent work on temporal reasoning with temporal uncertainty, preferences, and other extensions.
2019:
2019 PROMINENT PAPER AWARD was given to:
The Dropout Learning Algorithm
Pierre Baldi, Peter Sadowski
Artificial intelligence 210:1-122 (2014)
Dropout has become a key machine learning technique used mainly to avoid overfitting when training large neural networks. The mathematical analysis in the paper uncovers the properties that have made dropout a cornerstone in deep learning. The article also provides connections to other areas of statistics, and to the theory of ensemble learning and spiking neurons.
2019 CLASSIC PAPER AWARD was given to:
Between MDPs and Semi-MDPs: A Framework for Temporal Abstraction in Reinforcement Learning
Richard S. Sutton, Doina Precup, Satinder Singh
Artificial intelligence 112(1-2):52-89 (1999)
This is the seminal paper on options, a widely used framework in reinforcement learning (RL) for representing actions at different temporal scales and levels of abstraction. The option framework has shaped subsequent work in the area, and still defines the terms in which the problem of representation learning of hierarchical actions and knowledge is formulated and addressed in RL.
2018:
2018 PROMINENT PAPER AWARD was given to:
Conflict-driven answer set solving: From theory to practice
Martin Gebser, Benjamin Kaufmann, Torsten Schaub
Artificial intelligence 187: 52-89 (2012)
Answer set programming (ASP) provides a powerful compact language for expressing a number of combinatorial problems. The paper introduces a novel approach for computing answer sets of logic programs which is based on concepts successfully applied in Satisfiability (SAT) checking. The approach is implemented in the ASP solver clasp that has won several contests while extending the range of problems that can be modeled and solved effectively as answer set programs.
2018 CLASSIC PAPER AWARD was given to:
On the Acceptability of Arguments and its Fundamental Role in Nonmonotonic Reasoning, Logic Programming and n-Person Games
Phan Minh Dung
Artificial intelligence 77(2): 321-358 (1995)
This is the seminal paper on argumentation theory that laid the foundations for almost all subsequent work in the area. This rich and elegant argumentation framework is developed from a few simple abstract primitives and is used to establish a crisp and meaningful relation between argumentation and theories of non-monotonic reasoning, logic programming, social choice, and cooperative games
2017:
2017 PROMINENT PAPER AWARD was shared by the following two papers:
BabelNet: The automatic construction, evaluation and application of a wide-coverage multilingual semantic network
Roberto Navigli, Simone Paolo Ponzetto
Artificial intelligence 193: 217-250 (2012)
The prominent paper award for 2017 goes to two papers that have made outstanding outstanding contributions to the automatic construction of large knowledge bases and semantic networks from public domain sources such as Wikipedia and Wordnet. BabelNet is a multilingual lexical-semantic network that merges lexicographic information from open-source dictionaries. Thanks to BabelNet, computational lexical semantic tasks such as disambiguation, information extraction, question answering, and, more in general, text understanding, can be performed for a large number of languages while at the same time preserving the connections across languages, so as to enable the joint analysis and disambiguation of text in multiple languages.
YAGO2: A Spatially and Temporally Enhanced Knowledge Base from Wikipedia
Johannes Hoffart, Fabian M. Suchanek, Klaus Berberich, Gerhard Weikum
Artificial intelligence 194: 28-61 (2013)
YAGO2 is a conveniently searchable, large-scale, highly accurate knowledge base of common facts in machine-processable form. It is invaluable for making sense of internet content and for supporting tasks such as semantic search and text disambiguation, and, in general, for building truly intelligent agents. The YAGO2 paper builds on the earlier YAGO system and focusses on the integration and construction of the spatial and temporal dimension in knowledge bases. Both BabelNet and YAGO2 combine excellent science with a significant engineering effort.
They are not only enabling but also inspiring numerous other developments in artificial intelligence, natural language processing and the semantic web
The 2017 CLASSIC PAPER AWARD was given to:
Fast Planning Through Planning Graph Analysis
Avrim Blum, Merrick L. Furst
Artificial intelligence 90( 1-2):281-300 (1997)
This seminal paper changed the perspective on classical planning algorithms. Before the paper appeared, most of the planning approaches used back-chaining methods searching in plan space. Blum and Furst instead proposed to create a particular graph structure in an iterative deepening fashion for constraining
a backward search from the goal, leading to a dramatic performance increase. Although the specific planning algorithm proposed by the authors did not prevail, the ideas behind the algorithm and the empirical methodology adopted, inspired current approaches such as SAT-based planning and heuristic search-based planning methods. The work also demonstrated that it is quite worthwhile to go off the beaten path and take a fresh view on existing algorithmic problems.
2016:
The 2016 PROMINENT PAPER AWARD was given to:
Monte-Carlo Tree Search and Rapid Action Value Estimation in Computer Go
Sylvain Gelly and David Silver
Artificial Intelligence 175 (11):1856-1875 (2011)
Go is an ancient Chinese board game that has long been considered one of the great challenges in AI. While for a number of years computer programs have managed to beat the world’s leading human players in games like checkers and chess, the high level of intuition and evaluation required by Go made it tough for AI search methods to crack. This has changed in recent years, where the last milestone was the recent defeat of the legendary Go player Lee Se-dol by AlphaGo, a program developed by Google DeepMind. The previous milestone, however, that enabled this breakthrough, was achieved a decade ago through the use of Monte-Carlo Tree Search augmented with a number of enhancements. This led to programs that defeated human professional players and achieved master (dan) level in 9×9 Go. That work was reported in 2007 in two papers: one by Rémi Coulom in the Int. Computer Games Association Journal, the other by Sylvain Gelly and David Silver at the ICML 2007 conference. This AIJ paper is a follow-up of the latter, covering two of the enhancements: rapid action value estimation and heuristic initialization. These extensions led to a program that achieved master level in 19×19 Go for the first time.
The 2016 CLASSIC PAPER AWARD was given to:
Real-Time Heuristic Search
Richard E. Korf
Artificial intelligence 42 (2-3):189-211 (1990)
This is the seminal paper in real-time heuristic search over the basic state model considered in AI, where actions have deterministic effects and information is complete. While standard heuristic search methods are aimed at solving problems off-line, real-time search methods are used on-line for selecting the next action to do after some form of lookahead. Korf’s minimin and real-time A* algorithms take inspiration in the ideas underlying search in 2-player games, while Learning Real-time A* (LRTA*), where the heuristic values are updated dynamically during the search, was the first to capture two key properties: avoidance of loops and convergence to the optimal solution. LRTA* remains a key reference in the field, where a number of variants have been developed that work under slightly different assumptions, including the Real-time dynamic programming algorithm (RTDP), that can be regarded as generalization of LRTA* to Markov Decision Processes.
2015:
The 2015 PROMINENT PAPER AWARD was given to:
Label Ranking by Learning Pairwise Preferences
Eyke Hüllermeier , Johannes Fürnkranz , Weiwei Cheng , Klaus Brinker
Artificial Intelligence 172 (16-17):1897-1916 (2008)
This paper is a key paper in the area of preference learning. It studies the problem of label ranking, which is concerned with learning a mapping from instances to rankings over a finite number of labels. The authors introduce the Ranking by Pairwise Comparison algorithm (RPC), which first induces a binary preference relation and then uses this relation to derive a ranking. The paper contains appealing theoretical results (that RPC can minimize different loss functions) as well as empirical results (that RPC is competitive in terms of accuracy and superior in terms of efficiency).The paper shows the elegance and power of a natural and intuitively appealing approach. It has been influential in the field of preferences and preference learning.
The 2015 CLASSIC PAPER AWARD was given to:
Fusion, Propagation, and Structuring in Belief Networks
Judea Pearl
Artificial Intelligence 29 (3):241-288 (1986)
This is the seminal journal paper that introduced Bayesian networks and the distributed, linear-time, message-passing algorithm for belief propagation in singly-connected networks (including trees) . This work along with Pearl’s 1988 book, “Probabilistic Reasoning in Intelligent Systems”, sparked what some call the “probabilistic revolution” in AI. The impact of Bayesian networks and Bayesian networks algorithms on AI, Machine Learning, Information Theory, and Cognitive Science has been huge indeed, providing a representational and computational framework that relates probabilistic reasoning with graphs, graph topology with complexity bounds, and causal and evidential inference with directional information flow. By showing “how to do with probabilities what people say that you can’t”, the paper introduced key conceptual notions like the use of graphs for representing independence relations, and the use of independence relations for making exact probabilistic inference tractable on tree and tree-like graphs.
2014:
The 2014 PROMINENT PAPER AWARD was shared by the following two papers:
Reasoning about Preferences in Argumentation Frameworks
Sanjay Modgil
Artificial Intelligence 73 (9–10):901–934 (2009)
Argumentation is concerned with attempting to obtain rationally justifiable positions in the presence of conflicting evidence. Originating from the field of philosophy, argumentation research has now become a major topic for AI researchers. One of the key problems in argumentation is to develop a formal model and associated semantics for argumentation that can express the subtleties and nuances of argument and debate. Sanjay Modgil’s paper made a major contribution to this problem. His paper demonstrates how the canonical graph-based models used in abstract argumentation can be enriched to allow such notions as meta-argument, in which arguments can attack attacks. The paper motivates and presents this new model, and explores the relationship of the model to logic programming. Modgil’s work represents a key contribution to the argumentation domain, and an outstanding exemplar of work in this area.
Practical Solution Techniques for First-Order MDPs
Scott Sanner and Craig Boutilier,
Artificial Intelligence 173 (5–6):748–788 (2009)
Decision-theoretic planning problems are naturally represented using probabilistic first-order logic (e.g. PDDL) but are traditionally solved by first ‘grounding’ the problem. Unfortunately, such a ground representation grows polynomially with the number of domain objects and exponentially in predicate arity. In this seminal paper first-order MDPs are solved without grounding. Although the paper is wide-ranging and could serve as an introduction to this area, it also has the necessary technical depth, providing a clear explanation of solving techniques based on (i) symbolic dynamic programming and (ii) first-order linear programs. Moreover these techniques are implemented and empirically evaluated, showing good results on a range of planning problems. Representing and reasoning with first-order probabilistic theories (often called “lifted inference”) is a key research topic in AI; this paper constitutes a major advance to it.
The 2014 CLASSIC PAPER AWARD was given to:
A Logic for Default Reasoning
Ray Reiter
Artificial Intelligence 13 (1-2):81-132 (1980)
This seminal paper introduces and develops a mathematical theory of reasoning about defaults and exceptions that has become to be known as default logic. Reasoning about defaults is about drawing plausible conclusions in the absence of complete knowledge about a world. Default reasoning is a key component of everyday commonsense reasoning, and is essential in many computer systems. The central element of default logic is the definition of the extensions to a first-order theory induced by a set of defaults. Default logic is nonmonotonic, in the sense that conclusions justified by defaults may need to be retracted when new axioms are added. Reiter’s approach to default reasoning has been immensely influential. Not only it has made a significant impact on the field of knowledge representation, including its application to the frame problem and to other difficult issues in the theory of commonsense reasoning, but it has also made a significant impact on logic programming and underlies much current work on default reasoning including answer set programming. Overall, this article is one of the cornerstone publications of the knowledge representation research domain, and indeed of AI in general. The award committee is privileged to have the opportunity to recommend unanimously this paper as the recipient of the 2014 AIJ Classic Paper Award.
2013:
The 2013 PROMINENT PAPER AWARD was given to:
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 2013 CLASSIC PAPER AWARD was shared by 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 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:
The 2012 PROMINENT PAPER AWARD was given to:
Learning and Inferring Transportation Routines
Lin Liao, Donald J. Patterson, Dieter Fox, and Henry Kautz
Artificial Intelligence 171 (5–6):311–331 (2007)
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.
The CLASSIC PAPER AWARD was only initiated in 2013.