Monthly Archives: March 2009

Progress Report – Q1 2009

This is another progress report of my AI journey.  The top posts for the past quarter as follows:

Read More »

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.

What is Machine Learning?

Machine Learning is a sub-field of Artificial Intelligence.  Within Machine Learning there are subtopics:

  • Supervised Learning
  • Semi-Supervised Learning
  • Unsupervised Learning
  • Explanation Based Learning
  • Decision Tree Learning
  • Data Classification and Rule Induction
  • Inductive Logic Programming
  • Reinforcement Learning
  • Artificial Neural Networks
  • Conceptual Learning and General-to-Specific Learning (Version Space)
  • Statistical and Bayesian Learning
  • Computational Learning Theory
  • Genetic Algorithms and Evolutionary Computing
  • Belief Networks – Bayesian and Markov (Computational Uncertainty).

And there are other subfields not listed.  Please note that Support Vector Machines (SVM) are a form of supervised learning developed from Computational Learning Theory.

Reference Page

I have added a new reference page to track my reference materials that I mention in my blogs. It is a work in progress.

AIMA Part IV Acting Logically

Continuing my quest to read AI: Modern Approach (Russell & Norvig 1995), Part IV is the section on Acting Logically. Chapter 11 starts with a planning agent, and the authors develop the partial order planner (POP) algorithm. Please note the planning agent is not a theorem prover or a problem solving agent, but a specialized agent with a directed search in a planning space. The authors continue with the STRIPS language to develop the operators for a planning agent.

Chapter 12 starts with the discussion of current planners (circa 1995) and its use in industry and governement.  The planning topic continues with the hierarchical decomposition, generating the HD-POP algorithm.  The authors continue with conditional effects and universal quantification, leading to the  POP-DUNC algorithm.  Finally actions have resource constraints such as materials, cost, and time.

Lastly, Chapter 13 begins a discussion regarding conditional or contingency planning.  The algorithm for a conditional planning agent is presented as well as the algorithm for Conditional Partial Order Planner (CPOP).  Next is the section on a simple replanning agent, and an algorithm for a replanning agent is presented.  The algorithm for a situated planning agent is presented.  In summary, planning agents need to account for real world issues such as incomplete information, execution errors, or unmet preconditions and have contingency plans, quickly replan, or adjust the plan as it monitors the situation during the execution.

AI planners have been used in industry for job scheduling and by governments for job scheduling for the Hubble Telescope by NASA as well as for space missions by the ESA.  Other planners are discussed by history remarks in all three chapters.

The last two sections conclude knowledge and reasoning along with acting logically.  The basis is first order logic (FOL) along with situational calculus.  These topics work well with logic programming and the prolog programming language.

Knight’s Tour Revisited

In my previous posting of the Knight’s Tour problem, I had posted the following code:

% The knight's tour puzzle for an 8x8 board.
% Written by Robert Borrell
%
% To find solution,
%        type knight_tour([1,8], X). on interpreter line.
%
% Verify clause
%
verify(X,Y) :- X > 0 , X  0 , Y < 9.
%
% Knight move rules
%
knight_move([R,C],[X,Y]) :- X is R + 2 , Y is C + 1 , verify(X,Y).
knight_move([R,C],[X,Y]) :- X is R + 1 , Y is C + 2 , verify(X,Y).
knight_move([R,C],[X,Y]) :- X is R - 1 , Y is C + 2 , verify(X,Y).
knight_move([R,C],[X,Y]) :- X is R - 2 , Y is C + 1 , verify(X,Y).
knight_move([R,C],[X,Y]) :- X is R + 2 , Y is C - 1 , verify(X,Y).
knight_move([R,C],[X,Y]) :- X is R - 2 , Y is C - 1 , verify(X,Y).
knight_move([R,C],[X,Y]) :- X is R - 1 , Y is C - 2 , verify(X,Y).
knight_move([R,C],[X,Y]) :- X is R + 1 , Y is C - 2 , verify(X,Y).
%
% Depth Search Algorithm dervived from Programming in Prolog
%
go0(X,T,[X|T]).
go0(Place,T,R) :-
        knight_move(Place,Next),
        not(member(Next,T)),
        go0(Next,[Place|T],R).
%
% knight_tour clause
%
knight_tour(Start, Solution) :-
        go0(Start, [], R),
        length(R, Len),
        Len == 64,
        reverse(R, Solution).

In that posting, I stated that my code found a solution within 35 seconds and considered an improvement due to hardware technical reasons. However, I modified and improved the code by testing boundary conditions. I changed the verify clause from:

verify(X,Y) :- X > 0 , X  0 , Y < 9.

to test the boundary conditions instead as follows:

verify(9,_) :- !, fail.
verify(10,_) :- !, fail.
verify(0,_) :- !, fail.
verify(-1,_) :- !, fail.
verify(_,9) :- !, fail.
verify(_,10) :- !, fail.
verify(_,0) :- !, fail.
verify(_,-1) :- !, fail.
verify(_,_).

The modification improved by finding the first solution in six seconds of CPU utilization, which is a significant improved from 35 seconds.  The idea of testing the boundary came from reading the Othello chapter from Peter Norvig’s book Paradigms of Artificial Intelligence Programming as well as other sources for checking the border.  The new code, tested with SWI-Prolog, is as follows:

% The knight's tour puzzle for an 8x8 board.
% Written by Robert Borrell
%
% To find solution,
%        type knight_tour([1,8], X). on interpreter line.
%
% Verify clauses
%
verify(9,_) :- !, fail.
verify(10,_) :- !, fail.
verify(0,_) :- !, fail.
verify(-1,_) :- !, fail.
verify(_,9) :- !, fail.
verify(_,10) :- !, fail.
verify(_,0) :- !, fail.
verify(_,-1) :- !, fail.
verify(_,_).
%
% Knight move rules
%
knight_move([R,C],[X,Y]) :- X is R + 2 , Y is C + 1 , verify(X,Y).
knight_move([R,C],[X,Y]) :- X is R + 1 , Y is C + 2 , verify(X,Y).
knight_move([R,C],[X,Y]) :- X is R - 1 , Y is C + 2 , verify(X,Y).
knight_move([R,C],[X,Y]) :- X is R - 2 , Y is C + 1 , verify(X,Y).
knight_move([R,C],[X,Y]) :- X is R + 2 , Y is C - 1 , verify(X,Y).
knight_move([R,C],[X,Y]) :- X is R - 2 , Y is C - 1 , verify(X,Y).
knight_move([R,C],[X,Y]) :- X is R - 1 , Y is C - 2 , verify(X,Y).
knight_move([R,C],[X,Y]) :- X is R + 1 , Y is C - 2 , verify(X,Y).
%
% Depth Search Algorithm derived from Programming in Prolog
%
go0(X,T,[X|T]).
go0(Place,T,R) :-
        knight_move(Place,Next),
        not(member(Next,T)),
        go0(Next,[Place|T],R).
%
% knight_tour clause
%
knight_tour(Start, Solution) :-
        go0(Start, [], R),
        length(R, Len),
        Len == 64,
        reverse(R, Solution).

The above code generates open-circuit solutions. I have not checked for closed-circuit solutions. The first 14 solutions are found with just 2m07s of CPU utilization.

The test environment is Red Hat Linux v4.6, running in a VMWare session.

New AI Links

I have two new links to my AI websites section.  The new links are the Association of Uncertainty in Artificial Intelligence (AUAI) and the Association of Computional Learning Theory (COLT).  Both of these organizations sponsor the International Conference of Uncertainty in Artificial Intelligence and International Conference on Computional Learning Theory, respectively, which both are co-located with the ICML in Montreal, Canada this year.

Enjoy reviewing those websites.

AIMA Part III Knowledge and Reasoning

I just completed reading the last two chapters (9 & 10) of Part III, called Knowledge and Reasoning, of AI: Modern Approach (Russell & Norvig 1995).  Basically, Chapter 9 wraps up the previous material in Chapters 6 (Propositional Logic) and 7 (Predicate Calculus) by defining a generalized Modus Ponens and linked that Modus Ponens is a subset of the Resolution Refutation principle (Robinson 1965).  Resolution Refutation principle can be used to prove all statements in first order logic.  Also, Chapter 9 illustrates the Forward-Chaining, Backward-Chaining, Unification algorithms.  Finally, Chapter 10 discusses indexing knowledge bases, theorem provers, logic programming, productions systems, semantic networks, and meta systems.  The authors discuss the advantages and disadvantages of each systems and its primary application uses.  In both Chapters, the historical remarks are very informative along with relavent references.