fujin

A game-theoretic path planner.

Publication

	Krell, E., Carrillo, L. R. G., King, S. A., & Hespanha, J. P. (2020, July). 
	Game Theoretic Potential Field for Autonomous Water Surface Vehicle Navigation Using Weather Forecasts. 
	In 2020 American Control Conference (ACC) (pp. 2112-2117). IEEE.

Based on

Robot motion planning: A game-theoretic foundation. S. M. LaValle. Algorithmica, 26(3):430--465, 2000.

Directory Structure

fujin
├── test
│   ├── data
│   ├── games
│   ├── results
│   └── scripts
└── tools

• fujin: Python code for executing path planner.
• test: Sample data and outputs.
• games: Sample 2-player 0-sum games generated by path planner.
• scripts: For generating results to analyze planner's effectiveness.
• tools: Small programs that support path planner. May be useful for data preparation.

Solving 2-player, 0-sum Matrix Games

The code is set up such that a method parameter could be used to select a desired algorithm for solving matrix games. Only one is currently supported.

• Williams: Approximate, iterative solver.
  • Numeric selection flag: 0
  • Code: solver_tools.py -> solve_williams()
  • Source: code.activestate.com/recipes/496825-game-theory-payoff-matrix-solver/

Examples

A number of examples are found in test/scripts/

Tools

__Example Ta: Convert geotiffs of magnitude and direction to u,v components (all bands)

    python tools/magdir2uv \
        -m wind_mag.tif    \  # Input magnitude as this geotiff
        -d wind_dir.tif    \  # Input direction as this geotiff
        -u wind_u.tif      \  # Store u as this geotiff
        -v wind_v.tif      \  # Store v as this geotiff
        -s 3                  # Scale all magnitude by this float

__Example Tb: Solve a single game

   python solve_game \
       -g game.txt   \ # Input game as numpy txt archive
       -i 100          # Number of solver iterations

Misc

If you need to convert an ASCII map or force component grid to geotiff:

    gdal_translate -of "GTiff" fname.asc outname.tif

See StackOverflow for more information.

Todo

• Accept geotiff
• Accept grid of errors
• Accept grid of weights
• Measure solver results
• Track convergence
• Pandas convergence
• Graph convergence
• Graph path and actionspace
• Decide output format
• Convert to waypoints
• Specify subregion to solve
• 16 direction movement
• Save convergence history as pickle
• solvertools: assumes 16-way movement
• Need separate error for u and v components
• Need separate action selection for u and v components
• env_setup -> getComponentGrid: why does it accept band parameter, then use 1 anyway?