Project I: Moving-target Planner 
 
 

Out: Wed Sep 22

Due: Wed Oct 6

Files
Revised runtest with movie generation

Description: 

In this project, you are supposed to write a planner for the robot trying to catch a target. The planner should reside in the robotplanner.m file. Currently, the file contains a greedy planner that always moves the robot in the direction that decreases the distance in between the robot and the target. 

The robotplanner function: 

function[newrobotpos,state] = robotplanner(envmap, robotpos, targetpos,state); 

takes 3 parameters. envmap is the map of obstacles. envmap(x,y) = 0 is free, envmap(x,y) = 1 is obstacle. robotpos is the current position of the robot. targetpos is the current position of the target. State is an arbitrary data structure initialized by a call to createstate(envmap,robotpos,targetpos), where robotpos and targetpos are the respective initial positions.

The function should return the next position of the robot, as well as the state object for reuse. It should be any of the 8 cells adjacent to robotpos cell (including the diagonally adjacent cells). It cannot be a cell that is an obstacle or outside of the map boundaries (see current robotplanner for how it tests the validity of the next robot pose). 

The robotplanner must make produce a move within some arbitrary time limit (choosen by me). The time limit will default to 0.2 seconds, but your code must be able to handle different choices of the time limit. 

The directory contains few map files (map1.txt and map3.txt).

Here are few examples of running the tests: 

>> robotstart = [250 250];

>> targetstart = [400 400];

>> runtest('map3.txt', robotstart, targetstart); 

>> robotstart = [700 800];

>> targetstart = [700 1700];

>> runtest('map1.txt', robotstart, targetstart); 

Executing runtest command multiple times will show that sometimes the robot does catch the target, and sometimes it does not. The letters R and T indicate the current positions of the robot and target respectively. (Sometimes, they may appear as if they are on top of a boundary of an obstacle, but in reality they are not. The letters are just much bigger than the actual discretization of the map.)  

NOTE: to grade your homework and to evaluate the performance of your planner, I may use a different and larger maps from the ones in the directory, and a different strategy for how the target moves (different target planner). The only promise I can make is that the target will only move in four directions and the size of the map will not be larger than 5000 by 5000 cells. 
 

To submit:

Submit robot planner.m, createstate.m, videos of runs, and a few paragraphs describing the approach you took for the planner (i.e. what algorithm and with what parameters. Please post these on your class webpage.

Grading:

The grade will depend on two things: 

1. How well-founded and creative the approach is. In other words, can it guarantee completeness (to catch a target), can it provide suboptimality or optimality guarantees on the paths it produces, can it scale to large environments, can it plan within 1 second? 

2. How fast (and how consistently) it catches the target

Implementation Hints:

Timing You will want to use the tic() and toc() functions in matlab. Calling tic() starts a timer, and calling toc() will return the time since you last called tic(). Thus by calling tic() when you start robotplanner.m, you can check how much time you have used by calling toc()

Data Structures I highly recomend representing the graph with a number of arrays, each containing one data element of a node. Thus you may have one array to keep track of the cost of the optimal path to the goal, another to keep track of back pointers, etc. Even in the 5000x5000 map, the time MATLAB requires to allocate these arrays is insignificant

Reused State I have added a state object to the parameters of robotplanner, which is intended to allow for state to be reused after iterations. The state object is initialized by the createstate.m function, which is given the environment map, and the initial robot and target locations. I recomend storing state in a struct, which can be generated by calling

temp=struct('bar',{array parameter},'bar',number,.....).

The data members can then be retrived by calling temp.bar or temp.foo. While arrays and matricies need to be stored in a cell (i.e. inside of {}), temp.bar will return array or matrix within the cell, not the cell itself. Numbers can be stored directly.