Robotics in STEAM Education:
A Hands-On Journey with Graph
Theory Challenges
PID2021-122326OB-I00
Teresa Fernández Blanco
Antía Fernández López
Cristina Lois Prados
Erasmus+ BIP: Supporting curriculum through integrated STEAM Education practices
HOW DO KIDS SEE THE FUTURE?
HOW DO
"ADULTS" SEE
THE FUTURE?
https://youtu.be/G2emilxcHm8
WHAT TECHNOLOGIES HAVE THESE
MOVIES PREDICTED?
WHAT TECHNOLOGIES HAVE THESE
MOVIES PREDICTED?
Hologram Fingerprint reader Robot + mechanical arm Android
Exoskeleton 3D Printing Rocket AR
Holographic screen AI VR AI Android
VW
Cyber-pregnancy
WHICH IS OUR ROLE AS
TEACHERS IN THE
FUTURE OF SOCIETY
AND TECHNOLOGICAL
DEVELOPMENT?
CAN WE IGNORE AS
TEACHERS THE
TECHNOLOGICAL
INCLUSION IN
CLASSROOM?
CHALLENGE PRESENTATION
Is it possible nowadays to program an intelligent home delivery car?
In the following pictures we can see the city of Brno and an street map of an small part of it
We can find an area full of restaurants besides an urban area
Urban area Restaurants zone
CHALLENGE PRESENTAION
Is it possible nowadays to program an intelligent home delivery car?
Do you have any idea about how to model this situation?
MBOT2
CYBERPI
MBOT2
CYBERPI
MOTHERBOARD
MBOT2
CYBERPI
CHASIS
MOTHERBOARD
MBOT2
CYBERPI
CHASIS
MOTORS
MOTHERBOARD
WHEELS
MBOT2
CYBERPI
CHASIS
MOTORS
MOTHERBOARD
WHEELS
ULTRASONIC SENSOR
MBOT2
CYBERPI
CHASIS
MOTORS
MOTHERBOARD
WHEELS
ULTRASONIC SENSOR
RGB SENSOR
• WHICH CONTENTS
ARE WE WORKING?
• WHICH OTHER
PORPOSALS COULD
BE MADE WITH
THESE RESOURCES?
Urban area Restaurants zone
INTELLIGENT FOOD DELIVERY CAR (Model formulation)
Is it possible nowadays to program an intelligent home delivery car?
Do you have any idea about how to model this situation?
Urban area Restaurants zone
INTELLIGENT FOOD DELIVERY CAR (Model formulation)
Is it possible nowadays to program an intelligent home delivery car?
Do you have any idea about how to model this situation?
Urban area Restaurants zone
INTELLIGENT FOOD DELIVERY CAR (Model formulation)
Is it possible nowadays to program an intelligent home delivery car?
Do you have any idea about how to model this situation?
INTRODUCTION TO GRAPH THEORY
Problem of the Königsberg's bridges
Is it possible to pass throw all the bridges without crossing anyone two times?
Requirement: The path must start and end at the same point.
Kaliningrado, previously Königsberg
INTRODUCTION TO GRAPH THEORY
Problem of the Königsberg's bridges
Is it possible to pass throw all the bridges without crossing anyone two times?
Requirement: The path must start and end at the same point.
Kaliningrado, previously Königsberg Euler (1736)
INTRODUCTION TO GRAPH THEORY
Can you find a Hamiltonian path? Is it the shortest one?
A Hamiltonian path passes throw each vertex exactly once and returns to the departure node
INTRODUCTION TO GRAPH THEORY
Can you find a Hamiltonian path? Is it the shortest one?
A Hamiltonian path passes throw each vertex exactly once and returns to the departure node
Traveling salesman problem
Given a list of cities (nodes) and the distances (edges) between them, what is the shortest
possible path that visits each city (node) exactly once and returns to the departure city?
Famous because of the contrast between its simple formulation and the difficulty of finding and exact algorithm to solve it
INTELLIGENT FOOD DELIVERY CAR (Route optimization)
Can you find a "Hamiltonian path"?
Urban area
INTELLIGENT FOOD DELIVERY CAR (Route optimization)
Can you find a "Hamiltonian path"?
Restaurants area
INTELLIGENT HOME DELIVERY CAR (Route optimization)
Can you find a "Hamiltonian path"? Why?
Which is the maximum number of restaurants (nodes) that you can visit without
repeating anyone (starting and finishing the route at the blue triangle)?
Restaurants area
INTRODUCTION TO GRAPH THEORY
Traveling salesman problem (Algorithms)
An algorithm is as a sequence of instructions that can be used to solve a problem
If it provides an optimal solution (the most profitable), we say that the algorithm is exact
If it is almost optimal and we control the margin of error, the algorithm is approximated
If it produces a solution and we don't know how far is from the optimal one, it is heuristic
INTRODUCTION TO GRAPH THEORY
Traveling salesman problem (Algorithms)
An algorithm is as a sequence of instructions that can be used to solve a problem
If it provides an optimal solution (the most profitable), we say that the algorithm is exact
If it is almost optimal and we control the margin of error, the algorithm is approximated
If it produces a solution and we don't know how far is from the optimal one, it is heuristic
Coding Adventure: Ant and Slime Simulations (from 9' 8'' to 10' 8'')
ANT'S COLONY OPTIMIZATION ALGORITHM
INTELLIGENT FOOD DELIVERY CAR (Route optimization)
How can you generate a RANDOM "Hamiltonian path"?
Urban area
INTELLIGENT FOOD DELIVERY CAR (Route optimization)
How can you generate a
RANDOM "Hamiltonian path"?
Urban area Random letters generator
Registration of the Hamiltonian path
INTELLIGENT FOOD DELIVERY CAR (Route optimization)
Do you think that we have already
found the optimal solution?
Urban area
What is the probability of
succeding with such an
small number of iterations?
Random letters generator
Registration of the Hamiltonian path
INTELLIGENT FOOD DELIVERY CAR (Route optimization)
How can you generate a
RANDOM "Hamiltonian path"?
Restaurant area
INTELLIGENT FOOD DELIVERY CAR (Coding)
DECISIONS
- How to follow the road
- When there is a crossing, how to
know which direction to follow
- How to make stops at
food/delivery stations
ROLES
- Line-follow team (2 members)
- Programmers (2 members)
- Enviroment responsable (1 memmber)
TPACK
MKT
DIDACTICAL SUITABILITY
SAMR model
Acknowledgments. Project PID2021-122326OB-I00
financed by MCIN/AEI/10.13039/501100011033