previous day
next day
all days

View: session overviewtalk overview

08:45-10:40 Session 16: 6th ASP Competition Report - Tools & Applications
Location: Grand Kentucky Salon B
The Design of the Sixth Answer Set Programming Competition & Winners Announcement
Performance Tuning in Constraint Programming
SPEAKER: unknown

ABSTRACT. Performance analysis and tuning have been well established processes in software engineering in the realm of imperative programming. This work is a stepping stone towards establishing the standards of performance analysis in the realm of answer set programming -- a prominent constraint programming paradigm. In particular, we present and study the role of automatic configuration tools and human tuning in this process.

Interactive debugging of non-ground ASP programs

ABSTRACT. Answer Set Programming (ASP) is an expressive paradigm for problem solving. Although the basic syntax of ASP is not particularly difficult, the identification of (even trivial) mistakes may be painful and absorb a lot of time. The development of programs can be made faster and comfortable by resorting to an effective program debugger. In this paper we present a new interactive debugging method for ASP. The method points to a buggy non-ground rule identified by asking the programmer a sequence of questions on an expected answer set. The method has been implemented on top of the WASP solver. The tight integration with the solver allows to avoid efficiency problems due to the grounding blowup induced by modern reification-based debuggers.

Shift-design with Answer Set Programming

ABSTRACT. Answer Set Programming (ASP) is a powerful declarative programming paradigm which has been successfully applied to many different application domains. Recently, ASP has also proved successful for hard optimization problems like course timetabling. In this paper, we approach another important task, namely shift design problems. For that problem, one looks for an alignment of shifts in order to meet a required number of employees (which typically differs for different time periods) in such a way that over- and understaffing is minimized. We give ASP encodings of the shift design problem which to the best of our knowledge has not been addressed by ASP yet. Our experimental results demonstrate that ASP is capable of improving some of the best known solutions to real-world problems. On the other hand, other instances cannot be solved yet. Thus, shift design problems provide an interesting benchmark for further development of ASP systems.

11:05-12:35 Session 17: Joint ADT/LPNMR Session
Location: Grand Kentucky Salon B
Social Choice as a source of (Hard) Computational Problems

ABSTRACT. Social choice theory is the study of the representation and aggregation of (possibly conflicting) individual preferences.  In recent years, the study of computational social choice has bloomed and been applied in many areas including recommender systems and kidney exchanges. Two of the most impactful domains within social choice theory are voting and resource allocation.  Voting procedures have been used for thousands of years to make group decisions.  These procedures are finding new applications from aggregating disparate sensor data to combining recommendations in ensemble algorithms.  Resource allocation is a key area of study for both economics and computer science.  Results in resource allocation are applied every second for allocating computational resources on servers as well as allocating physical things such as airport runways and radio spectra.  We will survey a number of important domains in social choice theory and provide a survey of the key challenging and open problems in the field.

Pocket calculators for hard combinatorial search and optimization problems

ABSTRACT. Distinguishing features of pocket calculators are their ease of use, spectrum of operations, and effectiveness in evaluating arithmetic expressions.
The same role can be played by answer set solvers as regards solving hard combinatorial search and optimization problems.
I underpin this claim by illustrating the rich yet simple modeling language of Answer Set Programming, along with the versatility and effectiveness of its problem solving techniques.

Democratix: A Declarative Approach to Winner Determination

ABSTRACT. Computing the winners of an election is an important task in voting and preference aggregation. The declarative nature of answer-set programming (ASP) and the performance of state-of-the-art solvers render ASP very well-suited to tackle this problem. In this work we present a novel, reduction-based approach for a variety of voting rules, ranging from tractable cases to problems harder than NP. The encoded voting rules are put together in the extensible tool Democratix, which handles the computation of winners and is also available as a web application. To learn more about the capabilities and limits of the approach, the encodings are evaluated thoroughly on real-world data as well as on random instances.

Implementing preferences with asprin

ABSTRACT. asprin offers a framework for expressing and evaluating combinations of quantitative and qualitative preferences among the stable models of a logic program. In this paper, we demonstrate the generality and flexibility of the methodology by showing how easily existing preference relations can be implemented in asprin. Moreover, we show how the computation of optimal stable models can be boosted by using declarative heuristics. We empirically evaluate our contributions and contrast them with dedicated implementations. Finally, we detail key aspects of asprin's implementation.

14:00-15:40 Session 18: Applications I
Location: Grand Kentucky Salon B
Integrating ASP into ROS for Reasoning in Robots

ABSTRACT. Knowledge representation and reasoning capacities are vital to cognitive robotics because they provide higher level functionalities for reasoning about actions, environments, goals, perception, etc. Although Answer Set Programming (ASP) is well suited for modelling such functions, there was so far no seamless way to use ASP in a robotic setting. We address this shortcoming and show how a recently developed ASP system can be harnessed to provide appropriate reasoning capacities within a robotic system. To be more precise, we furnish a package integrating the new version of the ASP solver clingo with the popular open-source robotic middleware ROS. The resulting system, ROSoclingo, provides a generic way by which an ASP program can be used to control the behaviour of a robot and to respond to the results of the robot's actions.

Combining Heuristics for Configuration Problems Using Answer Set Programming
SPEAKER: Anna Ryabokon

ABSTRACT. This paper describes an abstract problem derived from a combination of SIEMENS product configuration problems encountered in practice. Often isolated parts of configuration problems can be solved by mapping them to well-studied problems for which efficient heuristics exist (graph coloring, bin-packing, etc.). Unfortunately, these heuristics may fail to work when applied to a problem which combines two or more sub problems. In the paper we show how to formulate a combined configuration problem in Answer Set Programming (ASP) and to solve it using heuristics à la hclasp. In addition, we present a novel method for heuristic generation based on a combination of greedy search with ASP that allows to improve the performance of an ASP solver.

Automated inference of rules with exception from past legal cases using ASP

ABSTRACT. In legal reasoning, different assumptions are often considered when reaching a final verdict and judgement outcomes strictly depend on these assumptions. In this paper, we propose an approach for generating a declarative model of judgements from past legal cases, that expresses a legal reasoning structure in terms of principle rules and exceptions. Using a logic-based reasoning technique, we are able to identify from given past cases different underlying defaults (legal assumptions) and compute judgements that (i) cover all possible cases (including past cases) within a given set of relevant factors, and (ii) can make deterministic predictions on final verdicts for unseen cases. The extracted declarative model of judgements can then be used to make automated inference of future judgements, and generate explanations of legal decisions.

Diagnosing Automatic Whitelisting for Dynamic Remarketing Ads Using Hybrid ASP
SPEAKER: Alex Brik

ABSTRACT. Hybrid ASP (H-ASP) is an extension of ASP that allows users to combine ASP type rules and numerical algorithms. Dynamic Remarketing Ads is Google's platform for serving ads customized based on past interactions with a user. In this paper we will describe the use of H-ASP to diagnose failures of the automatic whitelisting system for Dynamic Remarketing Ads. We will show that the diagnosing task is an instance of a computational pattern that we call the Branching Computational Pattern (BCP). We will then describe a Python H-ASP library (H-ASP PL) that allows to perform computations using a BCP, and we will describe a H-ASP PL program that solves the diagnosing problem.

16:10-17:10 Session 19: Invited Talk: Nada Lavrac
Location: Grand Kentucky Salon B
Invited Talk: Relational and Semantic Data Mining
SPEAKER: Nada Lavrač

ABSTRACT. Inductive Logic Programming (ILP) and Relational Data Mining (RDM) address the task of inducing models or patterns from multi-relational data. One of the established approaches to RDM is propositionalization, characterized by transforming a relational database into a single-table representation. After introducing ILP and RDM, the paper provides an overview of propositionalization algorithms, which have been made publicly available through the web-based ClowdFlows data mining platform. The paper concludes by presenting recent advances in Semantic Data Mining, characterized by exploiting relational background knowledge in the form of domain ontologies in the process of model and pattern construction.

17:10-18:00 Session 20: Applications II
Location: Grand Kentucky Salon B
OOASP: Connecting Object-oriented and Logic Programming

ABSTRACT. Most of contemporary software systems are implemented using an object-oriented approach. Modeling phases -- during which software engineers analyze requirements to the future system using some modeling language -- are an important part of the development process, since modeling errors are often hard to recognize and correct.

In this paper we present a framework which allows the integration of Answer Set Programming into the object-oriented software development process. OOASP supports reasoning about object-oriented software models and their instantiations. Preliminary results of the OOASP application in CSL Studio, which is a Siemens internal modeling environment for product configurators, show that it can be used as a lightweight approach to verify, create and transform instantiations of object models at runtime and to support the software development process during design and testing.

Mobile Robot Planning using Action Language BC with an Abstraction Hierarchy
SPEAKER: Shiqi Zhang

ABSTRACT. Planning in real-world environments can be challenging for intelligent robots due to incomplete domain knowledge that results from unpredictable domain dynamism, and due to lack of global observability. Action language BC can be used for planning by formalizing the preconditions and (direct and indirect) effects of actions, and is especially suited for planning in robotic domains by incorporating defaults with the incomplete domain knowledge. However, planning with BC is very computationally expensive, especially when action costs are considered. We introduce algorithm PlanHG for formalizing BC domains at different abstraction levels in order to trade optimality for significant efficiency improvement when aiming to minimize overall plan cost.We observe orders of magnitude improvement in efficiency compared to a standard “flat” planning approach.

19:30-21:30 Session : Banquet
Location: Grand Kentucky Salon C & D