Implementation of Bidirectional search available

After a week of crashed machines and painful recovery/upgrading efforts, I finally got around to implementing a version of the Bidrectional search described on page 79 of the text book. This can be found in aima.search.uninformed.BidirectionalSearch. A fairly comprehensive test driver for this can be found in aima.test.search.searches.BidirectionalSearchTest as the implementation turned out to be a little trickier/subtler than originally anticipated.

Chp 3 Additions to Bleeding Edge Code

Added implementations for:

Fig 3.1, pg 61 Simple-Problem-Solving-Agent: aima.search.framework.SimpleProblemSolvingAgent
Fig 3.2, pg 63 Romania: aima.search.map.SimplifiedRoadMapOfPartOfRomania

In addition added an implementation of the
Uniform-cost search from page 75.

A demo of these can be seen in:
aima.search.demos.MapDemo
which uses all the existing uninformed search algorithms. Currently considering writing an implementation of the BidirectionalSearch as well in order to round out all the searches discussed in Chapter 3 - fun fun :-)

Dr Ciaran O Reilly joins the Aima Java Project

Dr Ciaran (pronounced Keeraan) O' Reilly, a researcher in AI from the San Fransisco Bay Area, has joined the AIMA Java project.
Having another contributor to the code base is awesome! We are still working out the fiddly details like how to ensure the formatting conventions are shared etc, but Ciaran's code has been checked into the codebase and he has commit rights (though he is still having problems with the svn server at Google code).

Parsing changes for Version 1.0

After a small hiatus, I Started working on version 1.0. The focus will be on implementing the "logic arc" from chapters 8 thru 19. The propositional logic part has been done but first order logic and planning is very sparse.

One of the problems of working with logic in java is that one ends up writing custom parsers. I don't want to use parser generators (like jlex/cup), because that would increase the number of jars/libraries that users need to download. Thus the recursive descent parsers in aima java.

Coding the lexer and parser and associated visitors is very tedious and I was a little desperate to remove the tedium. One approach is to write an SExp parser that takes care of generic sexp parsing and another need specific parser that parses the resulting sexps into the required dtata structures. I've prototyped this and it does seem to work.

I am still stuck on visitors though. Most tree walking needs double despatch and "visitor" seems to be the only way to do this in Java. The code is f_ugly though.

Hosted on Google Project Hosting

Dr Norvig has moved the repositories of the Java and Python code to Google Project Hosting.

Version 0.9 of AIMA -Java is now official ,

[AIMA JAVA Pre Final] Implemented Q Learning Agent

This completes Chapter 21

[AIMA JAVA Pre Final] Implemented PassiveADPAgent And PassiveTDAgent

The Passive ADP Agent converges much faster than the PassiveTDAgent, which is as it should be.
The Alpha symbol was a bit confusing till I recognized it was the probability normalizing constant!(I mistook it for a learning constant like the ones in neural networks).

Now onto Q Learning!

[AIMA JAVA Pre Final] Implemented Policy Iteration

This completes Chapter 17

[AIMA JAVA Pre Final] Implemented Value Iteration

The code is now generic enough to handle any M by N environment with x ( >= 0 ) blocked squares. The MDP is derived out of the world structure. A further refinement might be to implement some kind of text file reader so that folks could design new worlds. I'll wait and see if there is enough demand for something like this.

AIMA JAVA Pre Final - Implemented CellWorld

checked into the google code repo.
Number of tests = 399.

AIMA JAVA Pre Final - Implemented Particle Filtering

This completes Chapter 15

AIMA JAVA Pre Final - (HMM) Fixed Lag Smoothing Implemented

I've duplicated the algorithm in the text (fig 15.6 in my edition), but this (algorithm, as published) is almost certainly wrong. The forward operation uses the latest (the t-d th would have made more sense) perception. This doesn't make too much sense.
The values don't match up with those generated by the foreward backward implementation (which is almost certainly working correctly).

Need to get the algorithm clarified by Dr N. Incredibly enough, there aren't too many resources online about this particular (variant of the) algorithm .

AIMA JAVA Pre Final - (HMM) Forward Backward Implemented

nice snippet of code. very powerful algorithm

AIMA JAVA Pre Final - Present Status

Working on Chapter 15.

Implemented an HMM with predict, update and forward.
The code for this (after extensive refactoring) is looking good.

I used an example from Probabilistic Robotics as an additional requirement for the HMM code, i.e, enable the HMM implementation to model a robot with uncertain sensors and stochastic actions. This has worked out well, as an HMM modelling a robot has to make provision for robot actions.

The example in AIMA models a passive observer trying to estimate the probability of rain from seeing whether his superior carries an umbrella or not. Unlike the robot, he has no action he can take that modifies the environment.

The present implementation models both these situations as can be seen from the unit test.

I've also implemented the code for single step smoothing (section 15.2 page 545 in my edition).

AIMA JAVA Pre Final - The Plan

I expect to post the pre final version of the AIMA java code to Dr Norvig at the end of this april/beginning of May.

This release will contain the code for Chapters 15(Probabilistic Reasoning),16 (Simple Decisions), 17(Complex Decisions) and 21 (Reinforcement Learning). I also need to fill in a few gaps in the code list. Plus bug fixes.


If anyone is having problems with the game playing code, do get the latest code . For some reason, the code at the site doesn't match with the code base though this code was written well before the last release.

The next release (AIMA Java Final) will focus on implementing the code for the "logic arc" ie chapters 9,10,11,12 and 19. The code for prepositional logic is already in place and has been extensively field tested, but I am not very happy about the FOL code. This will probably get rewritten.