This assignment was part of the 16-782 Planning and Decision-Making in Robotics course at Carnegie Mellon University. The goal was to develop a planner that allows a point robot to catch a moving target. During execution, the planner is given an 8-connected 2D gridworld where the robot can move at most one unit along the X and/or Y axes. Each cell in the grid is associated with the cost of moving through it, where this cost is a positive integer. Each map has a collision threshold specified for the planner and any cell with cost greater than this is considered an obstacle the robot cannot traverse. Also given are the start position of the robot and the trajectory of the moving target as a sequence of positions. The target moves at a speed of one step per second.
The task of the planner is to generate a path for the robot allowing it to catch the target with the least cost incurred. The cost is calculated as the sum of the costs of cells visited by the robot, each multiplied by the number of seconds the robot spends in that cell. After the last cell on its trajectory the target disappears, which gives the robot a limited amount of time to calculate a trajectory and intercept the target.
I designed a planner using weighted A* search; specifically, it’s a modified Learning Real-Time A* where I set a limit on the number of iterations performed (number of states expanded). The heuristic I used was a combination of weighted A* to the nearest trajectory point and the object itself if it was relatively close to the robot. To handle and keep track of the states I used linked lists for both the Open and Closed sets.
The planner is written in C++ and executed through the Mex function of MATLAB.
Map 1
The first map is composed of cells which are either traversable (shown in blue) or and obstacle (shown in red). The image on the left shows the start position of the robot and the target. Also shown is the trajectory of the target in dashed pink lines, with the end position shown towards the lower-middle. In this map the collision threshold is 100 for the red cells. The GIF on the right shows the robot finding the shortest path to the target along the trajectory and intercepting it.
Map 2
This map is slightly different where the cells have an associated cost ranging from 0 to 6200, meaning that as the color goes from blue to red (from 0 to 6200), the cost associated with that cell increases. Therefore it is less costly for the robot to travel in the blue cells than those with higher values; here the collision threshold is 6000. The GIF shows the robot again finding the shortest path to the target, intercepting it at the earliest possible point in the trajectory.
