Skip to content

Notes and examples from the answer set programming session at SPA 2013

Notifications You must be signed in to change notification settings

matt-thomson/answer-set-programming

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

4 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

This repository contains examples from the "Say what you want, not how you want it done: An Introduction to Declarative Programming in Answer Sets" session at SPA 2013.

The session was led by Willem van den Ende and Marina De Vos.

Declarative Programming

Traditional languages:

  • programmer needs to provide algorithm
  • needs verification

Declarative languages:

  • programmer provides requirements for problem and solution
  • program == specification

Advantages:

  • simple & quick to write
  • helps to understand problem
  • portable

Disadvantages:

  • slow
  • hard to learn

Key concept: time to solution

Fundamental concept: models, not proofs, represent solutions

Need techniques to compute models (not proofs) => ASP solvers

Good for solving search problems:

  • N queens problem
  • Error diagnoses for a faulty system
  • Route planning
  • Optimal code sequencess
  • Composing music (!)

Answer set programming

  • Programs are written in AnsProlog
  • Programs consist of rules (not statements)
  • Rules are of the form "conclusion :- condition"
  • If the condition is true, then the conclusion must be true
  • Using clingo as an answer set solver
  • clingo nameFile for one solution
  • clingo -n 0 nameFile for all solutions

Simple example - menu

  • Facts (no conclusion)
  • Rules (conclusion & condition)
  • Negation as failure (if condition is false then not a solution)

Simple example - family tree

  • Can express facts with different predicates and variables as (e.g.) mother(M, X).

Exercise - Tweety

Create a program for birds (in general) that can derive that birds can fly, but that makes an exception for penguins, since penguins are non-flying birds. Demonstrate your example with tweety the penguin and polly the parrot.

Extension: ostriches and birds with broken wings cannot fly.

Theory

Can define deduction rules to find the answer set.

Example - Seating Allocations

Uses choice rules to restrict the number of people on a table.

Exercise - Graph Colouring

Given a set of nodes and edges between these nodes, and a given set of colours, determine if you can colour the graph with the available colours such that connected nodes do not share the same colour.

e.g. given a set of countries and their neighbours, colour the map such that neighbouring countries have distinct colours.

About

Notes and examples from the answer set programming session at SPA 2013

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published