Progress Report – November 2009

The month of November was very productive.  I began the month reviewing the RRL paper.  From there I reviewed from [Luger and Stubblefield 1993] the blocks world and its Prolog version of the blocks world planner.  Next step was to take the algorithm in Chapter 2, Figure 2.14 from [Russell and Norvig 1995], and to create an agent frame work in Prolog.  Upon review of [Covington, Nute, and Vellino 1997], I was able to apply advanced prolog tips to the agent frame work.  My initial objective is to have a functional blocks world planner in an agent frame work.  The basic planner agent has been created and returns an action.  However, the planner agent needs to generate a plan and return each action from the plan.  This needs further development; in other words, a work in progress.  The final blocks world planner agent will be posted upon completion.

Advance Prolog Techniques

After doing some Prolog programming for a while, there are some useful advanced Prolog techniques. First, tail recursion is very powerful. With the tail recursion it allows the Prolog compiler can optimize code without having to save the pointer for backtracking.  This is useful since it does not build the stack with up and crash the program with stack overflow errors.

Second, the conversion of complex structures into a list using the Univ operator.  I have worked with some complex data structures in my agent code for the blocks world program.  By converting the data structure into a list, it was easy to process the required functors.  Then upon process completion, the list was converted back to a data structure.

Agent Framework

As part of my ongoing agent training, I re-read the agent environment algorithm in Chapter 2 of AIMA (Russell and Norvig, 1995). The key challenge is how to convert an algorithm with repeat and for loops into viable Prolog code. At first inspection, the implementation is best suited for a language with control loops built into the programming language (e.g., LISP). My primary Prolog books [Bratko 1990] and [Sterling and Shapiro 1994] did not provide the required help. However, upon rereading Prolog Programming In Depth (Covington, Nute, and Vellino 1997), I was able to figure out how to write loops.

Blocks World

In order to understand the RRL paper better, I began to review the blocks world.  So I went back to review [Luger & Stubblefield 1993] on the discussions on the blocks world.  It was mostly used to illustrate propositional and predicate calculus.  In addition, there was a section on robotic planning using the frame problem and STRIPS as tools.  I reviewed the code base for robotic planning written in prolog.  So I began to enumerate all the possible states in the three blocks world.  Afterwards, I designed an test on how to move from an initial state to goal state.  I wrote the initial state, the action, the next state, etc. until the goal state was achieved.  Indeed, this was very simple for three blocks.

The Art of Prolog

The book The Art of Prolog (Sterling and Shapiro 1994) is an excellent treatise in the subject of Logic Programming and Prolog.  The book is divided into four parts – Logic Programming, The Prolog Language, Advance Prolog Programming Techniques, and Applications.

Beginning with Logic Programming, chapter one provides the best introduction into Logic Programming as well as the first definition of the abstract interpreter for logic programming.  The definitons for term, functor, compound term, clause or rules, logic programs, and the meaning for logic programs are presented.  The summary is worth reading.

Advance Prolog Programming

Reading the comp.ai.prolog news group, I noticed the prolog FAQ did not make any references to any advance prolog programming websites.  Though it mentions the Craft of Prolog as the book for the advance reader, it was published before the ISO Prolog standard was finalized.  I have in my wish list in Amazon the book Prolog Programming in Depth by Michael Covington et. al (Fascimile edition), which seems from the table contents a book that could compliment the Bratko’s Prolog: Programming for Artificial Intelligence and The Art of Prolog.  Here is an example:

cycle(X) :-
   (    X < 1 -> true
        ;
        write(X),
        nl,
        X1 is X - 1,
        cycle(X1)
   ).

The above example is used to count down from X to 1.  In all the online tutorials, I have not seen example using the -> control construct.  I will on occasion will publish some prolog code.

Advice Language

Back in 1990, since my goal back then was to develop a chess playing computer algorithm using prolog, as part of my research, I stumbled into Max Bramer’s book Computer Game Playing: Theory and Practice.  In that book there was a chapter by Ivan Bratko called Knowledge-based problem-solving in AL3, which according to the book the article appeared in Machine Intelligence 10.  In summary the AL3 system was basically a production system for chess problem using the Donald Michie Advice Language concept and utilizing Bratko’s IF condition THEN action rule concept.  At that moment of time, many of the concepts presented in the paper were foreign to me, and unbeknownst to me, many of the ideas are presented in Bratko’s AI book (1990).

Wumpus World Revisited

I have noticed there has been many searches for the wumpus world problem.  The LISP version is located at the AIMA website.  The Prolog version by Professor Larry Holder is located at this URL, which is written for Quintus Prolog.  Both versions are based on the analysis by Stuart and Norvig’s book.

Knights Tour Part III

Once again, I am looking the knight’s tour problem again.  Upon a google search of the knight’s tour and prolog, I discovered there are other prolog implmentations (one solution was written in Turbo Prolog as well as a Common LISP implementation).  As of this time I only have downloaded copies of the other implementations, and I am not certain how efficient these implementations are.

One observation about this puzzle is the use of a heuristic and magic squares.  One approach is to implement a version with the warnsdorf heuristic.  The heuristic requires a look a head procedure to maximize the good squares.  I have little knowledge about this heuristic since it was published in 1823.  The second approach is to use the concept of magic squares to fine solutions quickly and efficiently.  This is useful; however, the implementation of these solutions into logic programming is the question as well as the Prolog implementation.

Logic Programming Prolog

I am reading the book Logic, Programming and Prolog (2nd ed).  After completing the preliminaries chapter, much of the material was familiar since it was defining predicate calculus and logical inferences.  The material is mathematically rigorous by authors Ulf Nilsson and Jan Maluszynski.  They develop a series of definitions to build the language of predicate calculus and inference.  The familiarity was due to my studies from the material presented in Luger and Stubblefield (1992), and Stewart and Norvig (1995).

The authors continue with the SLD-Resolution along with Unification.  They illustrate a unification algorithm as well as proof trees.  Afterwards negation is discussed; thus  they develop the SLDNF-Resolution.  The cut and mathematics is covered.  If used improperly, cuts can make programs unsound and yield false answers.  All this tied into logic programming theory.  The theorems and propostions come from various resources.  The goal of the book is teach programmers on how to write logic programs that are sound, correct, and finite.

I found this book interesting thus far and good introduction to logic programming and prolog.