# opof-grid2d
[OPOF](https://github.com/opoframework/opof) simple navigation domains in a 2D grid world to help users familiarize with OPOF. They also act as a sanity check for developing optimization algorithms.
[](https://github.com/opoframework/opof-grid2d/actions/workflows/build_and_test.yml)
`opof-grid2d` is maintained by the [Kavraki Lab](https://www.kavrakilab.org/) at Rice University.
### Installation
```console
$ pip install opof-grid2d
```
`opof-grid2d` is officially tested and supported for Python 3.9, 3.10, 3.11.
## Domain: `RandomWalk2D[size]`
<p align="left">
<img src="https://github.com/opoframework/opof-grid2d/blob/master/docs/_static/img/random_walk2d.svg?raw=true" width="250px"/>
</p>
```python
from opof_grid2d.domains import RandomWalk2D
domain = RandomWalk2D(11) # Creates a RandomWalk2D domain instance for a 11x11 board.
```
##### Description
An agent starts at a location (green) and moves in random directions according to some fixed probabilities until it reaches the goal (magenta).
When attempting to move _into_ an obstacle (black) or the borders of the grid, a step is spent but the position of the agent does not change.
The probability of moving in each direction is fixed across all steps.
##### Planner optimization problem
We want to find a generator that maps a problem instance $c$ (in this case, the combination of board layout and start and goal positions) into direction probabilities (in this case, vectors $\in \mathbb{R}^4$ with non-negative entries summing to $1$), such that the number of steps taken during the random
walk is minimized.
##### Planning objective
$\boldsymbol{f}(x; c)$ is given as $- steps / (4 \times size^2)$, where $steps$ is the number of steps taken to reach the goal. A maximum of $4 \times size^2$ steps are allowed.
##### Problem instance distribution
The training set and testing set each contain $1000$ problem instances, where the obstacle, start, and goal positions
are uniformly sampled.
## Domain: `Maze2D[size]`
<p align="left">
<img src="https://github.com/opoframework/opof-grid2d/blob/master/docs/_static/img/maze2d.svg?raw=true" width="250px"/>
</p>
```python
from opof_grid2d.domains import Maze2D
domain = Maze2D(11) # Creates a Maze2D domain instance for a 11x11 board.
```
##### Description
[A* search](https://en.wikipedia.org/wiki/A*_search_algorithm) is run against a _heuristic_ function $h(n)$ to find a path from the start (green) to the goal (green). The heuristic function determines the priority in which nodes are expanded (cells that are in darker red have a lower $g(n) + h(n)$ value, and have higher priority). The maze is assumed to be _perfect_, i.e., there is exactly one path between any two cells.
##### Planner optimization problem
We want to find a generator $G_\theta(c)$ that maps a problem instance $c$ (in this case, the combination of board layout and start and goal positions) to $h(n)$ (in this case, assignments of values $\in [0, size^2]$ to each of the $size^2$ cells) such that the number of nodes expanded in the A* search is minimized.
##### Planning objective
The planning objective $\boldsymbol{f}(x; c)$ is given as $- steps / n_{\mathrm{empty}}$, where $steps$ is the number of nodes expanded before finding the goal and $n_{\mathrm{empty}}$ is the number of obstacle-free cells.
##### Problem instance distribution
The training set and testing set each contain $1000$ problem instances, where the maze is generated using [Wilson's algorithm](https://dl.acm.org/doi/10.1145/237814.237880), and the start and goal positions are uniformly sampled.
## Citing
TBD
## License
`opof-grid2d` is licensed under the [BSD-3 license](https://github.com/opoframework/opof-grid2d/blob/master/LICENSE.md).
`opof-grid2d` is maintained by the [Kavraki Lab](https://www.kavrakilab.org/) at Rice University, funded in part by NSF RI 2008720 and Rice University funds.
Raw data
{
"_id": null,
"home_page": "https://github.com/opoframework/opof-grid2d",
"name": "opof-grid2d",
"maintainer": "",
"docs_url": null,
"requires_python": ">=3.9",
"maintainer_email": "",
"keywords": "opof,optimization,machine learning,reinforcement learning,planning,grid world,robotics",
"author": "Yiyuan Lee",
"author_email": "yiyuan.lee@rice.edu",
"download_url": "",
"platform": null,
"description": "# opof-grid2d\n\n[OPOF](https://github.com/opoframework/opof) simple navigation domains in a 2D grid world to help users familiarize with OPOF. They also act as a sanity check for developing optimization algorithms.\n\n[](https://github.com/opoframework/opof-grid2d/actions/workflows/build_and_test.yml)\n\n`opof-grid2d` is maintained by the [Kavraki Lab](https://www.kavrakilab.org/) at Rice University.\n\n### Installation\n```console\n$ pip install opof-grid2d\n```\n\n`opof-grid2d` is officially tested and supported for Python 3.9, 3.10, 3.11.\n\n## Domain: `RandomWalk2D[size]`\n<p align=\"left\">\n <img src=\"https://github.com/opoframework/opof-grid2d/blob/master/docs/_static/img/random_walk2d.svg?raw=true\" width=\"250px\"/>\n</p>\n\n```python\nfrom opof_grid2d.domains import RandomWalk2D\ndomain = RandomWalk2D(11) # Creates a RandomWalk2D domain instance for a 11x11 board.\n```\n\n##### Description\nAn agent starts at a location (green) and moves in random directions according to some fixed probabilities until it reaches the goal (magenta). \nWhen attempting to move _into_ an obstacle (black) or the borders of the grid, a step is spent but the position of the agent does not change. \nThe probability of moving in each direction is fixed across all steps. \n\n##### Planner optimization problem\nWe want to find a generator that maps a problem instance $c$ (in this case, the combination of board layout and start and goal positions) into direction probabilities (in this case, vectors $\\in \\mathbb{R}^4$ with non-negative entries summing to $1$), such that the number of steps taken during the random \nwalk is minimized.\n\n##### Planning objective\n$\\boldsymbol{f}(x; c)$ is given as $- steps / (4 \\times size^2)$, where $steps$ is the number of steps taken to reach the goal. A maximum of $4 \\times size^2$ steps are allowed.\n\n##### Problem instance distribution\nThe training set and testing set each contain $1000$ problem instances, where the obstacle, start, and goal positions \nare uniformly sampled. \n\n## Domain: `Maze2D[size]`\n<p align=\"left\">\n <img src=\"https://github.com/opoframework/opof-grid2d/blob/master/docs/_static/img/maze2d.svg?raw=true\" width=\"250px\"/>\n</p>\n\n```python\nfrom opof_grid2d.domains import Maze2D\ndomain = Maze2D(11) # Creates a Maze2D domain instance for a 11x11 board.\n```\n\n##### Description\n[A* search](https://en.wikipedia.org/wiki/A*_search_algorithm) is run against a _heuristic_ function $h(n)$ to find a path from the start (green) to the goal (green). The heuristic function determines the priority in which nodes are expanded (cells that are in darker red have a lower $g(n) + h(n)$ value, and have higher priority). The maze is assumed to be _perfect_, i.e., there is exactly one path between any two cells. \n\n##### Planner optimization problem\nWe want to find a generator $G_\\theta(c)$ that maps a problem instance $c$ (in this case, the combination of board layout and start and goal positions) to $h(n)$ (in this case, assignments of values $\\in [0, size^2]$ to each of the $size^2$ cells) such that the number of nodes expanded in the A* search is minimized. \n\n##### Planning objective\nThe planning objective $\\boldsymbol{f}(x; c)$ is given as $- steps / n_{\\mathrm{empty}}$, where $steps$ is the number of nodes expanded before finding the goal and $n_{\\mathrm{empty}}$ is the number of obstacle-free cells. \n\n##### Problem instance distribution\nThe training set and testing set each contain $1000$ problem instances, where the maze is generated using [Wilson's algorithm](https://dl.acm.org/doi/10.1145/237814.237880), and the start and goal positions are uniformly sampled.\n\n\n## Citing\n\nTBD\n\n## License\n\n`opof-grid2d` is licensed under the [BSD-3 license](https://github.com/opoframework/opof-grid2d/blob/master/LICENSE.md).\n\n`opof-grid2d` is maintained by the [Kavraki Lab](https://www.kavrakilab.org/) at Rice University, funded in part by NSF RI 2008720 and Rice University funds.\n",
"bugtrack_url": null,
"license": "BSD-3",
"summary": "OPOF domains for 2D grid worlds",
"version": "0.2.0",
"split_keywords": [
"opof",
"optimization",
"machine learning",
"reinforcement learning",
"planning",
"grid world",
"robotics"
],
"urls": [
{
"comment_text": "",
"digests": {
"blake2b_256": "ab7c351e7eb6bd414cf40d788e15f9a15d3538f099596da80a6459350e65512f",
"md5": "f7cc025ef3a9895e14c8503b92c18744",
"sha256": "6803ee5e0ad476cacca2ae1c53140dd706ad7c89e635a360d1b1feff74933390"
},
"downloads": -1,
"filename": "opof_grid2d-0.2.0-py3-none-any.whl",
"has_sig": false,
"md5_digest": "f7cc025ef3a9895e14c8503b92c18744",
"packagetype": "bdist_wheel",
"python_version": "py3",
"requires_python": ">=3.9",
"size": 18441112,
"upload_time": "2023-03-12T19:11:11",
"upload_time_iso_8601": "2023-03-12T19:11:11.167715Z",
"url": "https://files.pythonhosted.org/packages/ab/7c/351e7eb6bd414cf40d788e15f9a15d3538f099596da80a6459350e65512f/opof_grid2d-0.2.0-py3-none-any.whl",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2023-03-12 19:11:11",
"github": true,
"gitlab": false,
"bitbucket": false,
"github_user": "opoframework",
"github_project": "opof-grid2d",
"lcname": "opof-grid2d"
}
JSON
