Module 1.5

Route Finding

​

​

Living and Working with Artificial Intelligence

Developed for the AI4GA (Artificial Intelligence for Georgia) project funded by National Science Foundation awards DRL-2049029 and DRL-2048502.

This work is licensed under the Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License. https://creativecommons.org/licenses/by-nc-sa/4.0/

​

​

​

​

​

Find a route from Atlanta to Tifton

Warm-up Questions

2

Warm-up Question

​

​

How do autonomous robots and self-driving cars find their way through the world?

3

Autonomous robots and self-driving cars make and use maps of their worlds

4

Personal Connection:

What kinds of maps have

you used in the past?

5

6

7

8

9

Finding paths through the mall

Map of Georgia

How does a self-driving car know which route to follow?

10

How does Google Maps create directions for you?

11

Label for each city

Let’s create a representation a computer could use.

For each city, we’ll add a blue label and type the city name.

It’s called a “graph”.

12

For each city, we now need to add a node

Node - represents the location for each city

13

links - represent the roads connecting cities

​

Links connect nodes together

Now, we need to represent the roads that connect the cities, we’ll use:

Georgia cities graph

Route finding is�a graph search�problem.

14

Breadth-First Search

Today we will learn an algorithm called the “breadth-first search”.

Breadth-First means at each level, we examine all the neighboring cities to the ones just reached, before proceeding to the next level. We keep going until we reach our destination.

​

15

Breadth-First Search (Using Colors)

1. Color the starting city as level 0.
2. Find all the uncolored neighbors, and�color them using the next level’s color.
3. Repeat step 2 until you’ve colored�the destination city.

16

Level 0

Level 1

Level 2

Level 3

Level 4

How to get from Savannah to Valdosta: Level 0

Color our start city:�Savannah is level 0.

17

Level 0

Level 1

Which cities will be cities?

How to get from Savannah to Valdosta: Level 1

Color the cities reachable from Savannah as level 1.

18

Level 0

Level 1

Which cities will be cities?

Level 2

How to get from Savannah to Valdosta: Level 2

Color the uncolored neighbors of level 1 cities as level 2.

19

Macon

Level 0

Level 1

Level 2

Which cities will be cities?

Level 3

How to get from Savannah to Valdosta: Level 3

Color the uncolored neighbors of level 2 cities as level 3.

20

Macon

Atlanta

Level 0

Level 1

Level 2

Level 3

Which cities will be cities?

Level 4

How to get from Savannah to Valdosta: Level 4

Color the uncolored neighbors of level 3 cities as level 4.��This includes our destination city, Valdosta.

Yay!

21

Macon

Atlanta

Rome

Newnan

Level 0

Level 1

Level 2

Level 3

Level 4

There are still some cities left uncolored. Do we need to go to level 5?

How do you recover the solution path?

1. Start at the goal: Valdosta. It is at level 4. Write down the label of that node.�
2. Find a neighbor one level below. Write down its label and move to that node.�
3. Repeat step 2 until you reach the starting point (Savannah), at level 0.

22

Level 0

Level 1

Level 2

Level 3

Level 4

​

​

Recovering the solution path

Begin at the�destination (Valdosta) and work backwards�toward the start (Savannah).�

Then reverse the result.

23

Macon

Atlanta

Rome

Newnan

Level 0

Level 1

Level 2

Level 3

Level 4

Level 0

Level 1

Level 2

Level 3

Level 4

Often Forget to Recover the solution path

Begin at the�destination (Valdosta) and work backwards (decreasing the levels)�toward the start (Savannah).�

Then reverse the result.

24

Macon

Atlanta

Rome

Newnan

Level 0

Level 1

Level 2

Level 3

Level 4

Level 0

Level 1

Level 2

Level 3

Level 4

Savannah

Hinesville

​

Waycross

Brunswick

Valdosta

Backward path

Forward Path

ACTIVITY TIME

25

Worksheet Page 1: Columbus to Brunswick

ork with your partner. Try to color all of the appropriate nodes from Columbus to Brunswick. Remember: You want to color the neighboring cities one step at a time.

Pro-tip: Place your finger on first city. Trace the lines that leave the city. Those are the neighbors. This helps you not to miss any cities.

26

Level 0

Level 1

Level 2

Level 3

Level 4

Exercise: Columbus to Brunswick

Once you have finished coloring the nodes, you can trace backwards from the destination. Recover the solution!��Pro-tip: Be sure you do NOT repeat any colors when you trace for a solution.

27

Level 0

Albany

Level 1

Level 2

Level 3

Level 4

Solutions: Columbus to Brunswick

There are two solutions.

​

The choice is arbitrary.

28

Level 0

Albany

Level 1

Level 2

Level 3

Level 4

So let’s break down the Breadth-First Search Algorithm into steps

1. Make the starting city the root of the search tree (level 0).
2. For every node at the current level:
1. Find its neighbors that are not already in the tree.
2. Add those neighbors to the next level of the tree.
3. If one of the neighbors is the destination, exit.
3. Repeat step 2 for the next level of the tree.

29

AI4K12 Guideline 2-B-ii

Reflection:

Describe how to conduct a�breadth-first search

30

31

Breadth-First Search: Search Tree

Fun Fact: Breadth-first search can be used even when we don’t have a graph to color.

The algorithms works by constructing a search tree.

32

Let’s draw a search tree to find a route from Savannah to Valdosta

​

​

​

Let’s locate on the map

• Savannah
• Valdosta

33

Atlanta

Toccoa

Rome

Athens

Newnan

Augusta

LaGrange

Columbus

Albany

Bainbridge

Tifton

Valdosta

Macon

Milledgeville

Brunswick

Waycross

Warner Robins

McRae

Hinesville

Statesboro

Savannah

Breadth-First Search: Savannah to Valdosta

34

Savannah

Step 1: �Make the starting city the root of the search tree (level 0).

​

​

Tree Root

Breadth-First Search: Savannah to Valdosta

35

Savannah

Step 2: For every node at the current level:

• Find its neighbors that are not already in the tree.
• Add those neighbors to the next level of the tree.
• If one of the neighbors is the destination, exit.

​

What cities neighbor Savannah?

Current level

Breadth-First Search: Savannah to Valdosta

36

Savannah

Statesboro

Hinesville

Step 2: For every node at the current level:

• Find its neighbors that are not already in the tree.
• Add those neighbors to the next level of the tree.
• If one of the neighbors is the destination, exit.

Are we at our destination?

Current level

Breadth-First Search: Savannah to Valdosta

37

Savannah

Statesboro

Hinesville

Step 3: For every node at the current level:

• Find its neighbors that are not already in the tree.
• Add those neighbors to the next level of the tree.
• If one of the neighbors is the destination, exit.

​

Breadth-First Search: Savannah to Valdosta

38

Savannah

Statesboro

Hinesville

Augusta

Macon

McRae

Brunswick

What should we do next?

​

(Repeat the process again.)

Are we at our destination?

Breadth-First Search: Savannah to Valdosta

39

Savannah

Statesboro

Hinesville

Augusta

Macon

McRae

Brunswick

Milledgeville

Warner Robins

Atlanta

Waycross

Are we at our destination?

Breadth-First Search: Savannah to Valdosta

40

Savannah

Statesboro

Hinesville

Augusta

Macon

McRae

Brunswick

Milledgeville

Warner Robins

Atlanta

Waycross

Valdosta

Tifton

Columbus

Rome

Athens

Toccoa

Newnan

Are we at our destination?

Breadth-First Search: Savannah to Valdosta�Recovering the Solution Path

41

Savannah

Statesboro

Hinesville

Augusta

Macon

McRae

Brunswick

Milledgeville

Warner Robins

Atlanta

Waycross

Valdosta

Tifton

Columbus

Rome

Athens

Toccoa

Newnan

You try it: �Draw the search tree

Find a route from�Atlanta to�Warner Robins

42

Atlanta

Toccoa

Rome

Athens

Newnan

Augusta

LaGrange

Columbus

Albany

Bainbridge

Tifton

Valdosta

Macon

Milledgeville

Brunswick

Waycross

Warner Robins

McRae

Hinesville

Statesboro

Savannah

Level 0

Level 1

Level 2

Level 3

Level 4

Breadth-First Search: Atlanta to Warner Robins�Recovering the Solution Path

43

Atlanta

Agusta

Macon

Milledegeville

Warner Robins

Rome

Newnan

Toccoa

Athens

Legrange

Statesboro

Route/Path

• Atlanta
• Macon
• Warner Robins

44

TPS - summarize what you learned today

Recap

45

So far we’ve talked about maps and their representations, and an algorithm

that a self-driving car might use to navigate from one location to another.

​

We used labels, nodes, and links to create a graph of the state. Then used the breadth first search method to find a route from a starting location to a destination.

Recap

46

47

Other than a map for driving around a state, can you think of other kinds of maps a self-driving car or autonomous robot might create for themselves?

48

Other Applications for Route Finding

Autonomous robots might be given a map of a hotel, hospital, or warehouse.

​

Robot vacuum cleaners create a map of the home and you can use an app to see the map and adjust it.

49

Assessment:

Help Bloopaloop Junior Travel from Hinesville to Atlanta

​

​

​

Let’s locate on the map

• Hinesville to Atlanta

50

Atlanta

Toccoa

Rome

Athens

Newnan

Augusta

LaGrange

Columbus

Albany

Bainbridge

Tifton

Valdosta

Macon

Milledgeville

Brunswick

Waycross

Warner Robins

McRae

Hinesville

Statesboro

Savannah

My Dream Bot

Over the course of Unit 1, you will design your own dream robot.

Module 1.5: Route Finding

Imagine you robot needs to move.

How might your robot use “route finding”?

What map would your robot need to know or discover?

How would your robot find the best route? (pre-determined, breadth-first, etc)

Tip: Students should complete in their own Dream Bot slides

Module 1.6: Societal Impact

What are some concerns people might have about your robot’s impact on society?

What are some aspects of your robot (or things you could add to it) that would have positive impacts on society?

What type of work places or locations (industries) might be interested in using your robots?

Tip: Students should complete in their own Dream Bot slides