A robot that plans, tracks and learns
The problem
Build a grid-world robot that finds paths with A*, keeps track of its position from noisy sensor readings, plans under slippery moves with value iteration, and learns the same task with Q-learning.
Requirements
- Load grid maps with walls, a start, a goal and hazards from text
- Plan shortest paths with A* and compare the cells expanded with uniform-cost search
- Track the robot's position with a histogram filter from noisy colour readings
- Compute an optimal policy with value iteration when moves slip
- Learn a policy with Q-learning and compare it with the value-iteration policy
Technologies
- Python
- Heaps
- Probability
- Dynamic programming
- Reinforcement learning
Step by step
- Write the map loader and a function that prints maps with paths or policies on them.
- Implement A* and uniform-cost search and compare them on several maps.
- Add the histogram filter and test it on runs with known true positions.
- Implement value iteration with slippery moves and print the policy.
- Implement Q-learning with ε-greedy exploration and measure how many episodes it needs.
Expected result
A small robotics toolkit that shows planning, tracking and learning on the same maps.
How it is evaluated
- A* always finds a shortest path and expands no more cells than uniform-cost search
- The filter's most likely cell matches the true position on most test runs
- The learned policy matches the value-iteration policy on most cells
- Each part is a separate, tested module
Ways to improve it
- Let the robot localize and plan at the same time
- Add moving obstacles and replan as they move
- Replace the Q-table with a learned function of the robot's surroundings