Transcript Drawing the Maze - UCF Department of EECS

G.U.N.D.A.M.
BLAKE
DIDIER LESSAGE
GABRIEL
What is it?
 A robot whose primary function is solving mazes of
varying types while transmitting the layout of the
maze back to a computer/laptop to display said maze
to the user
 Maze will be custom built with a layout capable of
being changed to any type depending on the user’s
specifications
Motivation
Features
 Wall Detection
 Wireless Communication
 Maze Solving
 Discover entire maze layout
 Accept path inputs from user
 Forward and backward movement
 Isolated rotation
Parts Being Used
 Two IR Sensors for the sides
 Two ultrasonic sensors for the front and back
 RFM12B-S2 Wireless Transceiver
 Robot Chassis
 Java GUI Interface
Wireless Subsystem
-ROBOT MODULE
-COMPUTER MODULE
Robot Module
 PCB layout
 MSP430 Microcontroller



Interface with Main µC through SPI or I2C
RFM12B RF Transceiver
Interface with MSP430 through SPI
 Schematic
Computer Module
 PCB layout
 MSP430 Microcontroller


RFM12B RF Transceiver


Interface RF µC through SPI
CP2101 UART to USB


RF µController
Interface RF µC through UART to PC USB
Schematic
Wireless Protocol
 TX node (Robot Module)
 Initially Transmitting to Establish Connection
 RX node (Computer Module)
 Initially Listening to Establish Connection
 Collision Avoidance Algorithm
 Avoid TX or RX at the same time
Wireless Protocol
 Employ AES-128 on both the Robot and Computer
module


Data encryption of TX packets on each node
Data decryption of RX packets on each node
RF Microcontroller (MSP430)
 Encrypt data in AES-128 algorithm
 Read data from RF Module for RX
 Send data to RF Module for TX
 Specifications:
 SPI, I2C, and UART interface
 16-bit Architecture
RF Transceiver (RFM12B)
 Low power: 2.8-3.8V
 High data rate: up to 115.2kbps
 Programmable TX and RX bandwidth
 Automatic Frequency control
 SPI interface
 16 bit RX FIFO
 Two 8 bit TX data registers
RF Transceiver (RFM12B)
 FSK Modulation Scheme
 RSSI Strength indicator
 Operating Temp -40-85˚C
 At 433MHz bandwidth
 Max TX/RX current 24mA/13mA
 Range > 200m
UART to USB Bridge (CP2101)
 USB Bus powered powered: 4.0-5.25V
 Baud rate up to 921.6kbps
 On chip voltage regulator
 Virtual COM port for GUI
Range Finder Subsystem
-INFRARED SENSORS
-ULTRASONIC SENSORS
Infrared Range Finder (GP2D120)
 Operating Voltage 4.5V to 5.5V
 Operating Current 33 to 50mA
 Measures 4cm to 30cm
 Analog output
IR Range Finder Function
Output Voltage (V) vs. Reflected distance (cm)
Ultrasonic Range Finder
 Measures 15cm to 510cm
 Operating Voltage 8-12V
 Current consumption 14mA
 Ultrasonic Frequency 40kHz
 SPI/I2C interface
 Onboard ATtiny26 µController
Physical Maze
 Plastic, Wood, Metal, Rubber, and Paper reflect
ultrasonic waves.
 Things to consider:


Cost : Metal > Plastic > Wood
Easy of Manufacturing: Metal > Plastic > Wood
 Lap Joints
Lap Joint
Maze Layout
Nodes
 Nodes will be “placed” at intersections and turns.
These nodes will be stored in a list on the computer
side. The node will have information on their
location, the amount of neighbors they have if
discovered, and the distance between the neighbors.
 Information on how far the robot has traveled before
reaching an intersection or turn will be stored and
sent to the computer to allow for accurate
representation of the maze and its dimensions
Walls
 Using the information given to it by the robot itself,
the location and length of the walls will be able to be
determined as well as any turns and openings along
these walls. This information is then used to draw
out the actual maze.
GUI
 Maze will be presented in its own frame along with
options for the user to request either a maze be
solved (if not already), the maze be explored, or a
particular path be traversed or destination reached.
Maze Solving (Path Finding) Algorithms
 Wall Follower
 Simple maze solving solution that involves following the left
side of the maze, including any turns that may follow. Will be
the default maze solving method
 This solution is only valuable in certain maze situations. If the
entrance of the maze happens to lie in the center and not on
the outside edge, or if a wall happens to lie on its own with no
connections, it will fail
Maze Solving (Path Finding) Algorithm
 Tremaux
 This algorithm assigns values to paths according to how many
times it has been traversed. At a fork in the road, if there is a
path valued at 0, it will take it. If not, and the current path is a
1, it will backtrack and take the next smallest path value. If the
current path is a 2, the smallest valued fork will be taken. This
method will be used if it is determined that the maze cannot be
solved with the wall following method
Entrances and Exits
 There will be a single entrance and exit for the maze
 A check will be done to determine if the maze type
can be discovered simply through the entrance’s
characteristics. If surrounded by walls, it is safe to
determine that the robot is inside of the maze rather
than outside of it. This is a signal to use Tremaux, as
emphasized previously.
 Exits can be within or outside of the maze. A check
will be done to determine the distances on all sides.
If these sides exceed the pre-determined dimensions
of maze, we have found our exit.
Format of Information
 Upon reaching an intersection, along with placing a
node, the robot will write to the port how far it has
estimated its travel, the number of turns open to it
(left, right, straight ahead)
 The program will read this information and use it to
construct the next set of walls. Each path drawn out
will simply be two lines of a pre-determined width
between them
Classes
 Nodes
 Neighbors
 Location
 Dead ends
 Part of path
 Heuristic
 detDistDest()
 getLocation()
 getHeuristic()
 getDistCurr()
Classes
 Path
 Nodes
 Distance
 Final (bool)
 getNextNode()
 removeNode()
 isDest()
 isSource()
Classes
 Walls
 Location1
 Location2
 Length
 Width
 Stand Alone (Bool)
 getLoc1()
 getLoc2()
 getLength()
 getWidth()
Classes
 Robot
 Location
 State
Solving
 Exploring
 UserPath



getState()
getLoc()
Explore Maze
 The robot will explore and discover any and all paths
within the maze using a hacked version of the
Tremaux algorithm. Instead of having the sole
purpose of discovering an exit, a list of all nodes and
paths along with their number of times visited will be
stored. The robot will then work through this list and
make its way to each node using a combination of
Tremaux and A star.
User Input Path
 The user will be able to input a path for the robot to
take inside of the maze.
 The user can either input an exact path for the robot
to take or….
 …the user can simply select a destination and the
robot will use A* path finding to find the shortest
path to the destination.
A*
 Once a destination node is chosen, the algorithm takes




into account only the destination and any neighboring
nodes to the current position of the robot.
Cost (distance) of moving a node is calculated for each
neighboring node not blocked off by a wall
Estimated cost of reaching destination is then calculated
The smallest calculated distance and the node that has
achieved said distance is then chosen as the next node to
travel to in the pre-path.
Once a path has been chosen, the robot then traverses
the maze using the path
A*
 If user selects a location that is not a node, a new
node will be placed at the user’s desired location
 This is necessary to enable to algorithm to actually
find a path to the destination
Specified Path
 User can also highlight a path of nodes to traverse
for robot
 User will select nodes it wishes to be incorporated
within the path itself or simply draw out a general
line to follow
 If general line made, the program will determine any
and all nodes that are sufficiently close to path to
incorporate within the list of nodes needed to
traverse it
Path Completion
 Once the path is completed, program will store the
path (simply a list of nodes and the order they should
be traversed)
 The program will then write to a serial port to be
read by the robot itself
 Upon reaching a node specified by the program, the
robot will request the next instruction on whether to
turn or continue straight on its path. This check also
involves determining if the node it is currently at is
the destination
Progress
Research
Design
Hardware
Completed
Remaining
Software
Testing
0
20
40
60
80
100
120
Budget
Part
Model
Price
Blake
Didier
Gabriel
QUESTIONS?