DiagnostiCar (3) - Question & Answer Interface

This post aims to explain how to create an interactive shell so that users may answer questions when the reasoning system need user information. The reasoning engine will access the ask engine by an predicate (I will call it ask). An naive implementation of the ask predicate could be:

ask(X) :-
 write(X), write(' is true?'), nl,
 read(yes).

It works, but askable predicates will be asked every time the reasoner will need an information, even if it was previously answered. Another specific problem from DiagnostiCar constraints, was how to separate which information is from which user, considering we're at an web application environment. The simultaneous users access to the reasoning engine couldn't simply be locked while an user was giving an answer back, so we must find a smarter way to ask.

To remember info in Prolog, we will need to use dynamic relations to store the asked questions, for those who don't know about dynamic relations I will give a short explanation. If you want to know more, read the "Building Expert Systems in Prolog"[1] book.

Dynamic relations works similarly as a relational table in a relational database [2], but without a type scheme (although it's strongly recommended to make a convention). The informations required to create a dynamic relation are just it's name and arity. To declare a dynamic predicate you just need to run dynamic(Predicate). Once the relation is a dynamic one, you can store information (assert/1 or asserta/1) or delete information (use retract/1 and retractall/1) eg.: assert(foo(bar)). To query a dynamic predicate you just have to call it (it allows unification!) eg.: ?- foo(bar).  -> true. I made the following basic but illustrative example about Prolog DB:

create_account(Id, Ammount) :-
    assert(account(Id, Ammount)).
    
deposit(Id, Ammount) :-
    retract(account(Id, PrevAmmount)),
    NewAmmount is Ammount + PrevAmmount,
    assert(account(Id, NewAmmount)).
    
withdraw(Id, Ammount) :-
    account(Id, PrevAmmount),
    PrevAmmount >= Ammount,
    retract(account(Id, PrevAmmount)),
    NewAmmount is PrevAmmount - Ammount,
    assert(account(Id, NewAmmount)).

To test the predicates do some queries:

?- create_account(1, 1000).
true.

?- deposit(1, 200).
true.

?- account(Id, Ammount).
Id = 1,
Ammount = 1200.

?- withdraw(1, 400).
true.

?- withdraw(1, 20000).
false.

?- account(Id, Ammount).
Id = 1,
Ammount = 800.

The best solution found, to solve the concurrence and the question tracking, was to create predicates to read and write, so the webapp could obtain such information from the expert system. To avoid repeating the same questions, we will have to maintain a table with questions made, one with the answered questions and another to keep the answers from the users. Note that each relation needs to keep an user id to know from which user each information belongs to. The expert system question interface is the following:

% asked: UserId | Question
:- dynamic asked/2.
% asked: UserId | Question
:- dynamic askfor/2.
% known: UserId | Question | Fact
:- dynamic known/3.

% Predicate used by the expert system to ask.
ask(Uid, Question, Answer) :-
    known(Uid, Question, Answer).
ask(Uid, Question, _ ) :-
    not(asked(Uid,Question)),
    not(askfor(Uid,Question)),
    assert(askfor(Uid, Question)),
    fail.

% Predicate used by the web app to input users answers for a given qeustion.
answer(Uid, Question, [Answer | Answers]) :-
    assert(known(Uid, Question, Answer)),
    answer(Uid, Question, Answers).
answer(Uid, Question, []) :-
    assert(asked(Uid, Question)),
    retractall(askfor(Uid,Question)).

% Routine called by the webapp to clean the data from a user whose 
% session was expired.
cleanup(Uid) :-
    retractall(askfor(Uid,_)),
    retractall(known(Uid,_,_)),
    retractall(asked(Uid,_)).

Not that hard! I will try to tell all about the abductive reasoning on the next post.

[1] "Building Expert Systems in Prolog"

[2] SWI Database

DiagnostiCar (2) - Knowledge Representation Language

I'm giving sequence to the last post about the DiagnostiCar expert system. Today I'm going to specify the predicates to represent some domain specific knowledge.

Prolog has a helpful and clean syntax [1] (at least when you're used to :P) and it's easy to define new operators syntax in SWI [2]. Such feature improves the readability of the knowledge base.

To make an abductive reasoning we will need at least the logic operators 'and','or' and 'implies' to represent knowledge and chain it.

Our simple language will have the following syntax:

• known X. - Says that the sentence X must be true;
• X <- Y - X is caused by Y;
• X & Y - Is true if X and Y are true;
• X v Y - Is true if X or Y are true ('|' is already used by Prolog);
• assumable X - X can be assumed to prove something;
• askable X - X can be asked to the user;

Note that I'm not using the negation, because some dangerous particularities of Prolog negation as failure.

It's interesting to note the similarity if we represented with the defaul prefixed notation of Prolog predicades:

- known(X)
- <-(X,Y)
- &(X,Y)
- v(X,Y)
- assumable(X)
- askable(X)

Defining opertors increases the readabilty of the knowledge representation significantly. To redefine operators we will use the SWI predicate op/3 [2]. We can only run this predicate like:

:- op(910, xfy, &).

The op predicate has three fields op(+Precedence, +Type, :Name). The first one says the precendence of the operator (a number between 0 and 1200). The second is how the functor will be placed within it's "children nodes", for example: xfy let the functor between the arguments while xf let the functor after it's argument (remembering that you can only create unary or binary operators). For our representation language we will have:

:- discontiguous(     known/1 ). % The discontiguous predicate tells Prolog
:- discontiguous( assumable/1 ). % that the given predicate can be declared
:- discontiguous(   askable/1 ). % unsorted.

:- op(910, xfy,      &    ). % a higher priority with an infix notation
:- op(920, xfy,      v    ). % infix notation and lower priority than &
:- op(930, xfy,     <-    ). % infix notation
:- op(940,  fx,   known   ). % prefixed notation and lowest priority
:- op(940,  fx, assumable ). % prefixed notation and lowest priority
:- op(940,  fx,   askable ). % prefixed notation and lowest priority

Now let's model the car problems knowledge into our language (remember that Upper names are variables):

%
% DiagnostiCar - Knowledge Base
%

% Observe that implication is seen as the real sense of consequence <- cause.
known problem(crank_case_damaged) <- crank_case_damaged.
known problem(hydraulic_res_damaged) <- hydraulic_res_damaged.
known problem(brakes_res_damaged) <- brakes_res_damaged.
known problem(old_engine_oil) <- old_engine_oil & leak_color(black).

known leak(engine_oil) <- crank_case_damaged.
known leak(hydraulic_oil) <- hydraulic_res_damaged.
known leak(brakes_oil) <- brakes_res_damaged.

% Implications in false can be seen as constraints.
known oil(Oil) <- exists_leak(true) & leak(Oil).
known false <- oil(brakes_oil) & leak_color(Color) & Color \= green. 
known false <- oil(engine_oil) & leak_color(Color) & Color \= brown & Color \= black.
known false <- oil(hydraulic_oil) & leak_color(Color) & Color \= red.

% The assumable predicate asserts what will be can be suposed 
assumable crank_case_damaged.    
assumable hydraulic_res_damaged. % to prove something e else.
assumable brakes_res_damaged.
assumable old_engine_oil.

askable leak_color(Color). % Askable predicate asserts which information will be asked for the user.
askable exists_leak(TrueOrFalse). % The argument of the predicate will be unified with the answer.

known goal(X) <- problem(X). % The goal predicate is what we want to prove with the expert system.

That's all for now. On the next post I will explain the question and answer interface using the dynamic Prolog predicates.

[1] Prolog Syntax

[2] Prolog 'operator/3' documentation

DiagnostiCar (1) - Introduction

I'm here to tell my expirience with logic programming on a graduation project - DiagnostiCar.

The DiagnostiCar core feature was an expert system for giving hints to laypeople about their cars symptoms and their causes and consequences to avoid being deceived by mechanics (an habit of the job). Communication between the system and the users was conceived to happen with multiple choice questions forms and at the end the system gives the possible causes for the observed car characteristics.

This is a video of the DiagnostiCar expert system interface working:



Although there are many other interesting aspects about the DiagnostiCar, let's focus on the shell system. The expert system reasoning system used was abductive reasoning which is a kind of reasoning that tries to find a plausible cause (or a set of them) for a given fact occurrence [1][2]. Find the causes for a given observation is exactly what we need for diagnose car problems (the cause of the observable symptoms).

I choose to use Prolog not only because it's default support to first-order logic (although some logic limitations on negation [3]), but it has a nice support for pattern matching and syntax operator definition (most of the Prolog implementations). From the Prolog implementations I've picked SWI Prolog due to it's multi-thread support (necessary for a system running on a multiple user environment), stability and speed (not as fast as the YAP) [4].

To illustrate the process of development of the expert system we will restrict our diagnosis to the problems consisting of some oil leaks problem. Here are some of the knowledge about car diagnosis I will use as example in the next sections:

• A crank case, hydraulic oil reservoir and brakes fluid reservoir damaged are problems;
• The crank case damaged provokes leak of engine oil;
• The hydraulic reservoir damaged provokes leak of hydraulic system oil;
• The brakes fluid reservoir damaged provokes leak of engine oil; 
• If an oil is leaking it dirts the garage's floor.
• The brakes fluid is green.
• The hydraulic oil is red.
• The engine oil is black or brown.
• If the engine oil is black, then it needs to be changed.

For the next parts, it's good to know the basic about Prolog. A VERY good material about Prolog, it's a the book "Building Expert Systems in Prolog"[5] which guided through the realms of logic programming and the nasty api's documentations. It is also very pratical and full of examples to follow. It's also good see the SWI reference to check some SWI particularities[6].

[1] Abductive Logic Programming
[2] Abducive Reasoning
[3] Prolog Negation as Failure
[4] Prologs Implementation Comparisons
[5] "Building Expert Systems in Prolog"
[6] SWI Manual