TJHSST Senior Research Project Final Proposal: Pathfinding in Realistic Situations 2006-2007
Olex Ponomarenko November 2, 2006
My project will deal with maps and pathfinding. The primary goal of the project would be to use an extension of the A* search algorithm or a different search algorithm to find both the shortest distance path and the fastest path through a given graph - an abstract representation of a real life map. Eventually, I hope to include realistic artificial intelligence concepts such as speed limits and street lights. A random graph generator will also be created. You would be able to select two locations and have the program determine the shortest and the fastest paths through the map in a smart manner. Since parsing images of real maps would not be a very productive use of time, the maps themselves will be fairly abstract. This topic has obviously been covered in programs such as google maps and mapquest. But most such programs only consider the maximum speed limit. Some of the other important factors such as traffic lights and stop signs. There isn't a whole lot of research out there on complex graph traversal and pathfinding. I'll do my best to find similar work, but if I am not able to find any ideas whatsoever, or I find my project's scope too easy or too broad, I might have to change my program's scope. I will be working with the Python computer language. This language is very easy to use, very feature-rich, and fast because it is interpreted and not compiled like Java. I will start out from very basic maps and go on to more complex ones with added features. This should allow me to check my solutions manually in the early stages, and using slower but 100 % successful 1

searching techniques, ensuring that the program works perfectly. I will also create a Java program to display the randomly generated graph and solutions in order to avoid obvious errors. By advancing from smaller maps and fewer features to a more powerful program, I will be able to track my progress every few weeks. In the process of testing I may create a random map generator, which would help me test out new features and progress throughout the development phase in a very random fasion. In the end, I'm hoping to have a nice GUI to present the abstract concepts that I will be working on throughout the year. You will be able to use your mouse to select starting and destination points, and the path will be highlighted. These plans might force me to transfer a lot of my system code into java so that I won't have to deal with two languages at the same time.

2