Friday, November 24, 2006


Here is a list of some the projects I have been working on this semester:

Maze Solver: A program for Tablet PCs that allows the user to draw a maze on the screen using a stylus, and then finds the shortest path through the maze using A* search. For a simple maze the program only takes a few seconds to solve, but for more complex mazes it can take up to a few minutes (depending on processor speed). One advantage of using A* search for this problem is that it guarantees both completeness and optimality (it will find a path if it exists, and that path will be the shortest one possible). One of the best things about working on this project was the fact that our group got to borrow a Tablet PC from the CS department for the semester.

Text Adventure: A game called "Amnesia" written in Prolog. Text adventures are particularly easy to implement using Prolog because of built-in grammar support for processing natural languages. Although our game only used a very simple grammar system, it shows how powerful Prolog can be at natural language processing. Here is a copy of the game's source code (you will need a Prolog interpreter in order to play the game).

Parenting Lab Website: I redesigned the website at work. Check it out at The old version of the website can be found here.

Keyboard Optimization: This program generates keyboard layouts by minimizing the total finger travel distance required for a piece of text. We used three different local search configurations (hill climbing, random step, and simulated annealing). For relatively small pieces of text, the program can produce keyboard layouts that are significantly better than both QWERTY and Dvorak layouts. However, the program is also very computationally expensive, so it would take too long to find a layout for any substantial piece of text.

Chatterbot: This program is still in development. We are using Haskell to make a chatterbot based on the character Marvin (from The Hitchhiker's Guide to the Galaxy). Since this project involves natural language processing, I think it would have been much easier to implement using Prolog. Haskell is a functional programming language, so even basic tasks which would have been easy to accomplish using Prolog become unnecessarily confusing!
Post a Comment