Computer things

A brief intro to Answer Set Programming (ASP).

Warning: this is a rather isolated, conceptual point of view*.

If I were to create myself a robot slave, after dealing with all the perception and movement issues, I would want to give him some sort of brain. Now I don’t want a dumb robot – he needs to be able to have a (limited) understanding of the world around him and be able to reason about things so I don’t have to explain every little thing to him. However, if he tried to do something that I do not like, such as putting my cat in the microwave, I would like to be able to understand his ‘thoughts’ and ‘beliefs’ about the world so I could address this.

ASP is a logic based, non-monotonic language used to represent knowledge about the world and reason with it. A program has some facts, relations and rules about things (human readable! not just a bunch of numbers!). When given a goal or some facts and passed through a solver it can logically reason how to achieve that goal or how that fact occurred. As ASP is declarative, an ASP program does not need to be told how to accomplish its goal – given enough information about the world an ASP solver can work it out.

What do you mean by ‘declarative’?

If you’ve done programming before it was probably ‘imperative’ programming, where you tell the computer exactly how to do things and it does them. That is not how this works. Instead we give the computer a bunch of rules and constraints about its environment, a current state and a final state and the solver works out all the possible logical ways to get from the current state to the final state based off the rules and constraints.

And ‘non-monotonic’?

In this context this means that given new information we can retract previous beliefs. If the computer generated an explanation for a coffee cup appearing on my desk, it may come up with the belief that I put it there. If it were then told that Bob was using my desk today, it could form the new belief that Bob put the coffee cup there, not me.

Okay, so how do I write ASP?

A program consists of atoms, literals and rules. An atom ‘a’ is the smallest proposition in the program and can be true or false ( a false atom is prepended with a ‘-‘. Literals are either a or not a – where ‘not a’ means that we have no reason to believe that a is true).

For example, given the atom ‘light_on(hallway)’ I have four possible literals/beliefs:

  1.  The hallway light is on: ‘light_on(hallway)’.
  2.  The hallway light is not on (aka it is off): ‘-light_on(hallway)’.
  3.  It is not known if the hallway light is on: ‘not light_on(hallway)’.
  4.  It is not known if the hallway light is off: ‘not -light_on(hallway)’.

A rule is of the form ‘head ← body.’. If the body (one or more beliefs) is true then we can infer the head (a single belief) to be true. A rule with just the head, ‘head ←.’ , is called a fact and must always be true. Similarly, a rule with just the body ‘← body.’ must never be true.

Solving an ASP program generates an ‘answer set’ which is a collection of all the beliefs that we know and can infer – ie all the beliefs that satisfy all the rules of the program.

Using these (and glossing over a few other things we need to define) we can construct rules such as:

  • if the hallway light is on then the robot should turn it off: ‘robot(turn_off(hallway), time) :- light_on(hallway).’
  • if a person picks up an object that was on a table, the object is now in the person’s hand and not where it used to be: ‘location(object, person, time2) :- picks_up(person, object, time1), location(object, table, time1).’

The ability to be able to have unknown beliefs combined with non-monoticity allows us to reason with incomplete knowledge and have default assumptions:

  • an object will generally remain where it is: ‘location(object, place1, time+1) :- location(object, place1 time), not location(object, P, time+1), place(P).’

(If we know an object is at place1 at a give time – location(object, place1 time) – and that we do not have information where the object is at the next instant in time – not location(object, P, time+1), place(P) – then we can believe that the object stays at the same place – location(object, place1, time+1).)

  • most books belong in the study: ‘belongs_in(book1, study) :- not -belongs_in(book1, study).’

If we haven’t been told that this particular book doesn’t belong in the study – ‘ not -belongs_in(book1, study)’ – then assume that it does belong there – ‘belongs_in(book1, study)‘. If later on the robot gets some information that a cookbook belongs in the kitchen, it will use a combination of beliefs and rules:

  1. all cookbooks belong in the kitchen
  2. this book is a cookbook
  3. an object can only be in one place, so it cannot be in the study

As you may be able to infer from the above example, the solver looks for beliefs that do not invalidate any constraints and as such our constraints/rules need to be thought about carefully – using a formal structure helps a lot with this.

Action Language

No one is forcing you to write ASP such that it follows an action language, just as no one is stopping you from writing your own assembly language. However, it is what the convention is and some tools being developed will assume you have written your program in this way. Also, breaking down the rules, properties and relations of the environment into this formal structure helps with debugging, and breaking down the program into smaller chunks for automation/scripts (in my work with ASP we used reinforcement learning to learning new executability conditions, meaning they could easily be added into the existing knowledge base automatically.).

  • Causal laws: executing an action a in a given state defined by properties p 0 , …, p m causes the inertial fluent f in to be true. For example ‘If a robot puts down an object it
    no longer has the object’: putdown(R, O, L) causes − has object(R, O).
  • State constraints: a state defined by p 0 , …, p m also satisfies property f . For example ‘an entity cannot be above itself’: −above(E1, E2) if E1 = E2.
  • Executability conditions: its impossible for actions a 0 , …, a n to occur in the state defined by properties p 0 , …, p m . For example ‘a robot can only hold one object
    at a time’: impossible pickup(R, O1) if has object(R, O2), O1 ! = O2.

 

Logic programming languages aren’t known for their computational speed, and ASP is no exception. Typical solvers generate a complete answer set – i.e a belief for absolutely everything it knows about for all time steps – which grow insanely quickly. In terms of most uses this is not required and not wanted (as it slows things down massively) – I do believe partial solvers have/are being developed so we only need to reason about a particular subset of things.

* If you want the formal stuff, go read a textbook. I only spent a year dabbling with ASP in my third year of Engineering for a particular application (with no prior experience in formal logic, prologs, computer science etc) and this was almost a year ago – so take everything with a grain handful of salt.

 

Advertisements
Standard