The goals of this exercise are to:

• Implement a basic discrete map representation and map an environment (Week 1).
• Use this map to implement a basic path-planning algorithm to navigate autonomously (Week 2).

You need:

• A Sparki robot
• A working implementation of odometry
• The ArcBotics line following poster

## Overview

Mapping and navigation are standard primitives in autonomous robots. Although the different map representations and planning algorithms vary drastically in complexity, the problems remain the same: localization and sensing is uncertain, maps are quickly corrupted, and both mapping and navigation have to deal with limited on-board resources. In this exercise you will use Sparki’s floor sensors to map traces on the floor (the line following poster). You will initially use the line-following algorithm to keep odometry error to a minimum, and then explore what happens if you don’t relay on environmental features to explore the environment. You will then assume a map to be given to you and implement a simple shortest-path finding algorithm to navigate on this map.

## Instructions

1. Think about a suitable data structure to store a discrete representation of the environment. Be conscientious of its memory requirements and the limited resources on Sparki.
2. Write code to display the map on Sparki’s display.
3. Obtain a simple map of the closed loop from the “line following” exercise using the line following/odometry code.
4. Implement a different approach for mapping that does not rely on line following such as spiraling outward or “lawnmowing” that minimizes the expected error.
5. Bonus: use a bit-wise representation of free space to increase the resolution of your map.
6. Write code that (1) obtains the X-Y coordinate of each grid cell’s center and (2) provides the map grid coordinates for a float X-Y coordinate. (You can use the functions modf() and fmod().)
7. Use your map representation to hardcode a map like in the provided picture. Implement a shortest-path algorithm like Dijkstra or A*  to plan from the Start to the Goal marker.
8. Execute the path on the robot by moving to the center coordinate of each grid cell.

Map to be used in Question 7 and 8

Note: You should budget half a lab period for creating the map and one and a half lab periods for mapping.

## Deliverables

1. Provide a brief write-up on your mapping approach and the differences you observe when moving from line-following to an approach that does not depend on environmental features. Include a picture of the maps you obtained.
2. Provide a brief write-up explaining your path planning approach, and answer the following questions: How long does it take to find a shortest path on Sparki? What would you need to do to deal with dynamic obstacles? What would you need to do in order to plan also for the desired orientation of the robot.

Keep your write-up to a single page including figures.