Skip to content

Latest commit

 

History

History
93 lines (65 loc) · 3.01 KB

README.md

File metadata and controls

93 lines (65 loc) · 3.01 KB

fujin

A game-theoretic path planner.

poster

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?