In this project, you will demonstrate your understanding of dynamic memory and linked data structures (Chapter
10), and extend your skills in terms of program design, testing, and debugging. You will also learn about
route planning, and implement a simple route re-planning mechanism in preparation for the more principled
approaches that are introduced in comp20007 Design of Algorithms.
Grid-Based Route (Re-)Planning
Route planning is used in the navigation of autonomous agents, e.g., self-driving vehicles, robots, and humans
(think of mapping services). Grid-based route planning studies the problem of constructing a route from an initial
cell to a destination cell in a two-dimensional space subdivided into grid cells that are either blocked or empty.
Figure 1a shows an example grid of 10 rows and 10 columns, the initial cell at row 0 and column 0 denoted by I
(yes, we count from zero) and the destination (goal) cell at row 9 and column 9 denoted by G. The green arrows
show the planned moves to get from I to G that omit the blocks shown as orange squares.