Drawing the Maze - UCF Department of EECS

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 users 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 RF Controller Interface RF C through SPI

CP2101 UART to USB 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-85C 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 - U LT R A S O N I C S E N S O R S 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 entrances 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 users 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 Remaining Completed Software Testing

0 20 40 60 80 100

120 Budget Part Model Price Blake

Didier Gabriel QUESTIONS?

Recently Viewed Presentations

  • Graham Haywood - University of Cumbria

    Graham Haywood - University of Cumbria

    GRAHAM HAYWOOD. CUMBRIA LEP DIRECTOR. STRATEGIC ECONOMIC PLAN PRIORITIES. Nuclear and Energy Excellence. Advanced Manufacturing. Rural and Visitor Economy. M6 Strategic Connectivity
  • Chapter 13 Teams in Organizations Ryan McVay/Getty Images

    Chapter 13 Teams in Organizations Ryan McVay/Getty Images

    Chapter 13 Teams in Organizations Ryan McVay/Getty Images
  • Simple Invertebrates Review

    Simple Invertebrates Review

    Invertebrates. No tissues or organs. Live only in freshwater. ... Put the following steps of sponge reproduction in order. Grows into an adult. Sponge produces both sperm and egg cells. ... The roundworm has a digestive system with 2 openings.
  • Important Conversations Retiree Permits Kenneth Kimball & Therese

    Important Conversations Retiree Permits Kenneth Kimball & Therese

    transport.tamu.edu. Important Conversations. Retiree Permits. Texas A&M Transportation Services. Kenneth Kimball & Therese Kucera. As the university grows, Transportation Services would like to start the discussion about services or policies that create inefficiencies or are provided at no cost.
  • Računalo kroz povijest - CARNetov Portal za škole

    Računalo kroz povijest - CARNetov Portal za škole

    Računalo kroz povijest Rana pomagala za računanje Računanje je staro koliko i čovječanstvo. Prvi znakovi kojima su ljudi bilježili članove plemena, stoku, zemljište, vrijeme urezivani su u kamenu, na drvenim stupovima i sl. Prvo računalo u svijetu je poznati "Stonehenge".
  • Signal-Theoretic Representations of Appearance

    Signal-Theoretic Representations of Appearance

    Foundations of Computer Graphics (Spring 2012) CS 184, Lecture 6: OpenGL 1 http://inst.eecs.berkeley.edu/~cs184
  • chp 1 - ccsfmarketing.com

    chp 1 - ccsfmarketing.com

    There is a gift-giving norm of reciprocity. Gift giving is a form of economic exchange in which the giver transfers and item of value to a recipient, who must reciprocate. Gift giving also involves a symbolic exchange. Gift giving ritual...
  • Life Science Chapter 11

    Life Science Chapter 11

    Arial Garamond Wingdings Calibri Arial Black Times-Bold Times-Roman Times New Roman Theme1 1_Theme1 Life Science Chapter 11 Plant Classification Advanced Seed Producing The Typical Vascular Plant Class - Gymnospermae Class Angiospermae Seed Types Monocot vs. Dicot Plant Responses and Growth...