AI Final Project: Mars Pathfinder Simulation using MotorJ - 09/12/2007, 20:16Today I handed in our AI project, this project was made using C/C++ and MotorJ.
In our AI class, an important part we saw was the different search algorithms, which can be used for many applications: from a chatbot (fellow classmates made a chatbot using ALICE) to the automatic navigation system found in the (perhaps aptly named) Mars Pathfinder Missions robots.
And, since I am a NASA freak, that's exactly what we tried to simulate.
Using OpenGL, C/C++, SDL and friends, we used MotorJ to create a program that would be able to find the most "convenient" path across a 3D terrain.
NASA, of course, uses infinitely more advanced algorithms, which take into account situations such as driving over rocks, excessive sliding and tilting dangers, etc. All that is described in this link:
http://marsrovers.jpl.nasa.gov/technology/is_autonomous_mobility.html (there's an 18 MB Quicktime movie which explains all that is taken into account and how the newest rovers - Spirit and Opportunity - are able to break their predecessors' lifetime autonomous driving record in a single day).
Our project was much simpler - first, we didn't send a golf-cart sized robot to Mars. We didn't send anything, in fact, to Mars :P. So we didn't take stereo pictures to correlate and analyze. Instead, we got an image from the famous Cydonia region ("The face on Mars") and also an image file describing the topography of Cydonia in grayscale (white pixels denote the most elevated regions), and we loaded it and turned it into a 3D terrain a la 'lanjobot 63 1/3'.
Those images were obtained from the Malin Space Science Systems website: http://www.msss.com/education/facepage/face.html. We rescaled them and colored them as we needed, and we loaded them into the engine.
We used a huge panorama texture rescaled and cut to four 512x256 images to do the environment mapping ("skybox").
Using the OpenGL C API, I created the Mars Pathfinder robot model, planning it first in 2D using a DIA diagram to resemble as much as possible the images (many of which are artists' conceptions) available on the web.
I didn't use Blender because currenty MotorJ can load only .OBJ models (ProjectOvejota), and the OBJ-exporting plugin in Blender doesn't export the materials or the textures, just the geometry, which leaves the work half-done.
After loading the terrain it is processed to create a one-dimensional array of "vector3" data (x,y,z points) and two-dimensional array of linked-list elements (called list_node in MotorJ) each containing a linked list with a custom data structure called "connection". This data structure contains a pointer to one of the "list_node"s in the two-dimensional array, and the cost of travelling there from the current node. Each node has up to eight connections, each for one of the eight possible neighbouring cells in the two-dimensional array. This was done to be able to keep the pathfinding algorithm sufficiently abstract to be employed in future programs, perhaps in 3D, without changing it.
The blue dots represent the nodes' positional data:
The "connection" data type was suggested by Iván Medina, its final implementation proposed by me and the connection-establishing process mostly implemented by Iván and me.
Here's a rough diagram etched in Xournal at 1 am prior to the project hand-in date:
The algorithm we used is something close to A*, yet we didn't use A* because we had trouble understanding the literature. The algorithm we implemented starts by adding the start node to a list and setting it as the "current node".
Then it calculates the distance from each of the "current node"'s neighbours to the goal node. It also adds the cost of travelling to that neighbouring node from the current node. Then it selects the lowest costing node and adds it to the list described in the starting step, which in the end will store the route followed by the algorithm. There are a few adjustments to this step: if the connection has been used, it is not considered. If the neighbouring node is the goal node, it is selected regardless of its cost. When the goal is reached, the algorithm stops searching and returns the list of nodes that make up the route.
When F10 is pressed, the engine shows the Mars Pathfinder model following the route that was found using the algorithm.
We also implemented a double viewport, in a "picture-in-picture" style. This was done using two glViewport calls, drawing the scene two times and using the Stencil buffer so the big viewport wouldn't draw over the small one.
Some OpenGL speed-up tricks were used so the scene could be drawn twice at 60 fps while keeping the processor happy: OpenGL Drawing lists (http://www.lighthouse3d.com/opengl/displaylists/), for the terrain, and OpenGL Vertex Arrays (http://www.opengl.org/documentation/specs/version1.1/glspec1.1/node21.html), for the node dots (who would think drawing each dot "by hand" would take so much time?).
I will try to implement these speed-up tricks in ProjectOvejota when I find some time, so that the models are displayed faster and with less processor usage.
As of this writing, while the project compiles perfectly in both GNU/Linux and Windows, the Windows version lacks a controlling terminal, necessary to specify the initial and final nodes to the pathfinding algorithm, so I will release a modified version for Windows ASAP, but meanwhile if you use GNU/Linux, the source and an executable are available in the link at the bottom.
National Autonomous University of Mexico (Universidad Nacional Autónoma de México - UNAM)
Faculty of Engineering (Facultad de Ingeniería)
december 8th, 2007
Project: "Mars Pathfinder Simulation"
Subject: Artificial Intelligence
Professor: Muñoz Gutiérrez Stalin
- Valenzuela Roca Alejandro
- Medina Vázquez Iván
- Hernández Pérez Sarah
- García Arias Omar
Unless otherwise specified, each source file is licensed under the GNU GPL license (The ones that do specify are LGPL).
Please see GPL and LGPL terms.
All the images are public domain (obtained from NASA), under fair use (the ones obtained from the Malin Space Science Systems website), or under Creative Commons CC-by-NC 3.0.
IA2008-1/mars_pathfinder -source - gnu_linux - FreeBSD - MotorJ.zip
< Back to blog