In the previous discussion regarding the depth-first search, I provided prolog code for the program. In my research, I asked the following:
Because the current maze puzzle has only one solution, can the maze puzzle be modified to contain additional exit nodes so that the depth-first-search program can test for additional solutions?
While reading Artificial Intelligence Techniques in Prolog (Shoham 1994), in the Search chapter, the author writes generic search algorithms. For example, the depth first search algorithm passes the name of the function connecting the nodes in the graph. That is very interesting since in other Prolog books, the authors customizes the search algorithm to the problem. As a result of this information, I simply modify a puzzle from book and incorporated the generic depth first search algorithm. I took and modified the maze problem in Chapter 8 from Covington’s book.
Another interesting concept from 1994. The chapter has four sections covering difference lists, difference structures, dictionaries, and queues. The power behind this concept is unification. The append operation against difference lists is completed in linear time. Difference structures is similar to difference lists. Queues are very self explanatory. I will analyze existing Prolog programs to verify if incomplete data structures will improve the execution.
In the Relational Reinforcement Learning [Dzeroski et. al.1998 and Dzeroski et. al. 2001], I reviewed the prolog code segments. By definition, the state is a list of grounded terms. The pre/2 predicate is intended to show the predictions are met in a similar fashion as in the STRIPS implementation. If the given state, the pre/2 produces the move/2 term. The delta/3 predicate produces the next state given the current state and move term. My objective is to take this prolog code segments and implement it into SWI-Prolog.
As I continue my reading of the Art of Prolog, in Chapter 14, the authors focus on Non-deterministic Programming. I was reading about non-deterministic programming in prolog as a programming technique. The generate and test approach to logic programming allows the generation of solution X and it gets tested. I used a similar technique in my knight tour’s implementation. The authors implement a blocks world using a depth first search to find path solutions without regard on whether a path or state had been visited or not. The solution has 20 steps to implement the initial state to the final state. The authors offered additional Prolog clauses to guide the search by avoiding already visited states, which leads to a three step solution.
Once again I am attempting to finish books such as The Art of Prolog. Also, I am working with Introduction to Bayesian Analysis and Decision. From Google scholar, I found an article on Temporal Relational Reinforcement Learning, which in turn lead to other articles of interest.
From the first book I completed Section 2 for which the author covers the core of Prolog programming language. Techniques such as accumulators and tail recursion are discussed. The section ends with programming style and debugging techniques.
Finally, I have completed the blocks world planner agent code. The code runs under SWI-Prolog version v5.8.1. The three blocks world was tested. Other block worlds world can used by simply modifying the initial and goal states. The environment code was based on the AIMA environment algorithm and agent planner code was based on Luger’s implementation with some modifications due to the data structures and the separation between the agent planner and its update function. This is the first step toward the RRL. I will continue with RL experience by studying [Sutton and Barto 1998].
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.
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.
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.
