Catch Me If You Can

Overview

This project presents using two different type of path finding algorithm to intercept the target: A-start algorithm and RRT algorithm.

Mazes

In this project, there are a myriad of maps, ranging from small maps (6x8) to extremely large maps (5000*50000) [1]. Here are some of the mazes that we use:

Map 0 (small map)

Approaches

In this project, we use A-start algorithm and RRT algorithm to intercept the target.

For the A-start algorithm, we use Manhattan distance as our heuristic function.

For the RRT algorithm, we use two slightly different values for $\epsilon$ (the distance between the current point and the new random point). For RRT1, the value of $\epsilon$ is 1.4, whereas that of RRT2 is porportional to the size of the map, i.e., the larger the size of the map, the larger the value of $\epsilon$ is.

Results

Intercepting the target using A-star in Map 0

 

Intercepting the target using RRT2 in Map 6

 

Result of A-Star Algorithm

Algorithm	Map	Steps	Avg. Time
A-star	Map 0	8	5.9*E-3
	Map 1	1281	10.5
	Map 2	16	4.4*E-2
	Map 3	257	0.86
	Map 4	9	5.6*E-3
	Map 5	NaN	NaN
	Map 6	76	0.57
	Map 7	NaN	NaN
	Map 1B	NaN	NaN
	Map 3B	NaN	NaN
	Map 3C	NaN	NaN

Result of RRT2 Algorithm

Algorithm	Map	Avg. Steps	Avg. Time	Avg. Iterations
RRT2	Map 0	7	4.6*E-3	34.3
	Map 1	1419	1.3	834.3
	Map 2	15.3	2.9*E-2	427.7
	Map 3	403	2.8	667.7
	Map 4	9	8.3*E-2	142
	Map 5	1019.3	7.7	6412.7
	Map 6	16	4.4*E-2	2994.3
	Map 7	NaN	NaN	NaN
	Map 1B	4461.7	293.1	51874.3
	Map 3B	719.3	49.6	5194.3
	Map 3C	1278.6	29.1	2941

Reference

1. UCSD ECE276B Planning & Learning in Robotics