Read Me

GridMDP - Stochastically generates grid-world MDP and solve them with various algorithms


Copyright (C) 2008 Florent Teichteil-Koenigbsuch and Guillaume Infantes

GridMDP is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

This is mainly both an educational and a research software for people who work
on Markov Decision Processes. This software automatically generates a random
grid of given size with random obstacles and random rewards, that can be solved
by many popular algorithms like VI (value iteration), LAO*, RTDP and more. New
algorithms can be easily added thanks to the object inheritance diagram of the
code.

Two classes of problems can be generated:

	- shortest stochastic path problems (SSP): generates a single initial state
	  and a single goal state ; each transition costs 1 except the ones arriving
	  in the goal state that cost nothing
	
	- general problems (GNL): generates random rewards at random states
	
Heuristics used in heuristic algorithms depend on the problem class. For SSP
problems, the Manhattan distance is used. For GNL problems, a uniform
upper-bound of the value function based on the maximum reward is used.

Three modes are allowed:

	- GUI mode ('gridmdp_gui' program): draws the generated grid in a GLUT
	  window and shows the real-time evolution of many parameters during the
	  optimization (value of the initial state, Bellman's error, reachable
	  states, updated states...)
	
	- NOGUI mode ('gridmdp_nogui' program): does not draw the grid on the
	  screen, but is more efficient and allows a fair comparisons of algorithms
	  (since the cost of drawing different parameters in the GUI mode depends on
	  the algorithm)
	
	- TEST mode ('gridmdp_tests' program): does not draw the grid on the screen,
	  and outputs a LaTeX/TikZ figure comparing different algorithms that is
	  useful for writing scientific papers
	
Please see the help of each program for more details: <program-name> --help


INSTALLATION INSTRUCTIONS

To compile the software, you need:

	- a recent version of the BOOST library (version 1.35 at least should be
	  OK), available at http://www.boost.org/
	
	- the GLUT library, available at http://www.opengl.org/resources/libraries/glut/

Comments are welcome and new algorithms implementation are welcome.

Florent Teichteil <florent.teichteil@onera.fr> and Guillaume Infantes <guillaume.infantes@onera.fr>