4. Design Details

DETAILS OF DESIGN  

The broader project consists of 2 major systems, namely Hardware Design and Software Design. Each of the systems is further subdivided into a total of 8 subsystems. Following is the breakdown of the two systems.

                                     I.            Hardware Design

                                      a.       Obstacle Avoidance and Path Finding

                                      b.      Control System and Vehicle Dynamics

                                      c.       Robot Localization

                                      d.      Power Management

                                      e.       Overall Integrated System

                                    II.            Software Design

                                      a.       Range Determination and Path Finding

                                      b.      Robot Mobility and Speed Control

                                      c.       Machine Learning and Mice Algorithm

The following sections of this report will provide the details of each of the subsystems that are outlined above.

Hardware Design

The hardware design portion of the project deals with the physical abilities of the project. In order to successfully accomplish the goal (solve a maze) of this project, the robot must also be able to provide localization data at any given time. Robot localization is discussed in detail in the Robot Localization subsection.

Obstacle Avoidance and Path Finding

The obstacle avoidance system provides the hardware necessary to study the surrounding (i.e. maze walls) of the robot. Once the environment has been successfully acknowledged, any physical obstacles can be avoided via software algorithm.

Six IR sensors were used to accomplish the tasks of this system. Each of the IR sensors provides analog voltage based upon the separation distance between an object (maze wall) and the specific sensor. Once all six of the IR sensors provide their respective analog voltages, the following directional surrounds of the robot’s environment is sensed. 

1.      Forward view from the robot

2.      Right side view from the robot

3.      Right diagonal view from the robot

4.      Left side view from the robot

5.      Left diagonal view from the robot

Successful sensing of the robot environment provides specific details of the maze that are necessary to solve the maze.

Control System and Vehicle Dynamics

The control system of the robot provides the hardware necessary to precisely control movements of the robot. This robot uses 2 motors as part of a RWD (Rear Wheel Drive) system. The speed of each wheel determines the robot’s direction and speed of travel. Therefore, it is absolute necessary to be able to monitor the speed of each of the wheels. This is accomplished by using a wheel encoder for both wheels.

Two quadrature encoders were used in this project. The advantage of using a quadrature encoder versus other types of encoders is that quadrature encoders provide direction (forward or reverse) of travel in addition to dual RPM readings by using two sensors (i.e. IR in this project). The dual readings provide better accuracy when determining the RPM of the wheels.

A motor driver is used to interface the digital signal controller (DSC) to the motors. Combining the motor driver, motors, quadrature encoders and a DSC forms a closed-loop (feedback) control system.

Robot Localization

Robot localization is a very big part of this project. In order to make decisions about the next move (i.e. which way to travel, speed, etc.), the robot must know exactly where it is in the maze at any given time. Once the robot understands its current position and orientation, it can determine which way to travel.

In this project, robot localization is calculated using the IR sensors that were discussed in the Obstacle Avoidance and Path Finding subsection and the wheel encoders that were discussed in the Control System and Vehicle Dynamics subsection. Initially the robot develops an internal map of the maze based on the size of the maze, starting location, and destination location. The initial internal maze that is developed only knows about each grid of the maze. Initially the robot does not know where each wall is at. However, the robot does know how far it should travel to reach the next grid.

In reality there are walls in the maze. The robot uses the IR sensors to avoid collisions with the walls, and it uses the wheel encoders to calculate how far and in which direction it has traveled. As the robot explores the maze, it uses these sensing abilities to map its location and orientation, while developing a better internal outline of the maze in the software. 

Although the robot localization is computed in software, it cannot be accomplished without proper hardware. The hardware needs to provide specific data that makes it possible for software to perform its calculation. To keep the design simple and efficiently utilize available hardware resources, no new hardware was used. The goal was achieved using the IR sensors and quadrature encoders. This not only minimized power consumption, but also reduced the possibility of electromagnetic interference.

Power Management

The robot that was designed and built has a relatively small footprint. Therefore, hardware packaging was a very challenging task. It was important to accomplish the goal of this subsystem using batteries that are physically small and can provide enough power for each of the subsystems for a reasonable time. In addition, there was the need to provide both 3.3V and 5V. In a smaller package, consisting of components running at a high frequency, satisfying EMC (Electromagnetic Compatibility) requirements is another challenge.

After evaluating all options, including power requirement for each of the hardware and available resources, a 9V battery was chosen to be the primary source of power for this robot. 

The following specifies the max power requirements for each of the electronics.

From the above chart it is clear that three regulated power source is required, providing 3.3V, 5V, and 5V-9V. Since PWM (Pulse Width Modulation) is to be used with the motor to control wheel speed, the 5V-9V source is easily achievable with PWM and 9V primary source. Therefore, only two (3.3V, 5V) regulated power sources needs to be designed.

A 9V form-factor batteries can provide only so much (typically up to 300mAh) mAh. The mAh divided by total current draw at any time provides how long the electronics can be powered from a fully charged battery at that moment and current draw. To reduce power waste, switching voltage regulators were chosen to obtain desired output voltages (3.3V, 5V). Switching regulators uses a PWM method to turn OFF and ON the internal circuit at a predefined frequency to obtain the desired output voltage. This approach significantly reduces power waste.

3.3V @ 1.5A

Following is the overall schematic of the regulated power source that provides 3.3V at up to 1.5A.

The inductor is used as an energy storage device. When the internal switch of the switching voltage regulator is switched ON, the current in the inductor ramps up and energy is stored. When the switch is OFF, the current is released to the load.

A switching voltage regulator was used to accomplish the goal of this regulated power circuit. The switching voltage regulator is made by Recom (Part # R-78B3.3-1.5).  The regulator has minimum power efficiency of 88% under maximum input voltage, and maximum power efficiency of 91% under minimum input voltage. 

The calculation of the inductor in the above circuit is as follows:

Switching frequency, f, of the switching voltage regulator = 380 KHz

Input voltage range of the switching voltage regulator = 4.75V – 18V

Maximum input voltage, Vi, of the switching voltage regulator = 18V

Output voltage, Vo, of the switching voltage regulator = 3.3V

Maximum output current of the switching voltage regulator = 1.5A

Duty cycle, D = Vo/Vi  = 3.3V/18V  = 0.1833

Voltage across inductor (switch is ON) = VI=   Vi - Vo = 18V – 3.3V = 14.7V

Voltage across inductor (switch is OFF) = VI = -V0  = -3.3V

Ripple current of the switching regulator = 150 mA

The amount by which the current changes during a switching cycle is known as the ripple current. Ripple current is defined as:

VL = L di/dt

VL is the voltage across the inductor

di is the ripple current

dt is the duration for which the voltage is applied

L = VL dt/di  

L = 47.2µH

The closest available inductor that was found when ordering components was 47.4 µH.

C1 is the output capacitor for dynamic load stability. The switching voltage regulator datasheet recommended a 100µF for the output.

D5 is a protection diode used to protect the switching voltage regulator from reverse current. It is schottky diode with maximum forward voltage of 490mV at forward current of 2A.

5V @ 1.5A

The following is the overall schematic of the regulated power source that provides 5V at up to 1.5A.

A switching voltage regulator was used to accomplish the goal of this regulated power circuit. The switching voltage regulator is made by Recom (Part # R-78B5.0-1.5).  The regulator has minimum power efficiency of 92% under maximum input voltage, and maximum power efficiency of 94% under minimum input voltage. 

The following is the calculation of the inductor in the above circuit.

Switching frequency, f, of the switching voltage regulator = 380 KHz

Input voltage range of the switching voltage regulator = 4.75V – 18V

Maximum input voltage, Vi, of the switching voltage regulator = 18V

Output voltage, Vo, of the switching voltage regulator = 5V

Maximum output current of the switching voltage regulator = 1.5A

Duty cycle, D =  Vo/ Vi = 3.3V/18V  = 0.2777

Voltage across inductor (switch is ON) = VL  = Vo - Vi = 18V – 5V = 13V

Voltage across inductor (switch is OFF) = VL = -Vi = -5V

Ripple current of the switching regulator = 150 mA

The amount by which the current changes during a switching cycle is known as the ripple current. Ripple current is defined as:

VL = L di/dt

is the voltage across the inductor

di is the ripple current

dt is the duration for which the voltage is applied

L = VL dt/di   

L = 40µH

C3 is the output capacitor for dynamic load stability. The switching voltage regulator datasheet recommended a 100µF for the output.

D10 is a protection diode used to protect the switching voltage regulator from reverse current. It is schottky diode with maximum forward voltage of 490mV at forward current of 2A.

Overall Integrated System

Upon successful design of each of the subsystems, they were integrated into the overall robotic platform as shown in the system block diagram.

For simplicity, the power sources are not included in the above block diagram. However, each of the subsystems is powered as needed.

The dsPIC33EP512MC806 was chosen as the digital signal controller (DSC) for this robot. This DSC has 512 KB of program memory, which makes it ideal for future software development and enhancement.  The DSC also provides two internal oscillators, 7.37 MHz and 32 KHz. In addition, the DSC has plenty of A/D (Analog to Digital Converters) and PWM (Pulse Width Modulation) channels to interface with the IR sensors and motors. One of the most important features of this DSC is the built in QEI (Quadrature Encoder Interface). This very useful feature makes integrating the Quadrature Encoders with rest of the system very simple and efficient in the software and hardware.

The dsPIC33EP512MC806 is not available in DIP (Dual Inline Package). Therefore, it is very difficult to test it on breadboard. One of the possible ways to test this DSC was to use a DIP header. However, the available time, cost and complexity made this a less viable option. This constraint made the design more challenging and required a lot of evaluation. After a full review was completed, a preliminary schematic was designed. The design was then presented to the project advisor to receive feedback. Fortunately, only few changes were needed, including the addition of 8 (4 for each motor) protection diodes for the Motor Driver. This addition made sure the Motor Driver is safe regardless of which direction the motor spins.  Following shows the schematic of one of the motors and its interface with the protection diode. Note that J2 is a terminal block to interface with the actual motor.

PCB (Printed Circuit Board) Design

Once the prototype schematic has been designed, all the components were laid out on an integrated PCB (Printed Circuit Board). One of the biggest challenges of PCB design was EMC (Electromagnetic Interference). The design consisted of both digital and analog circuitry (switching voltage regulators). In addition, there were also two inductors in the design. DC components are particularly subjected to transients caused by current interruptions that routinely occur when circuits are de-energized. Simply closing and opening a switch can cause unintended radio-frequency interference. In the design of this robot this characteristic is exercised by the switching regulators. To make sure the circuit always has consistent current, the inductors are being used. When the switch from the switching voltage regulators are closed the inductor stores energy. When the switch is closed, the inductor provides the current necessary to eliminate switching transient. Plus, digital electronics is highly prone to noise due to EMI. Therefore, the layout of the PCB needed to incorporate EMC issues by keeping the digital electronics away from analog electronics and use bypass capacitors where needed.

A few of the possible approaches to eliminating EMC issues are the following:

·         Large separation within components

·         Twisted paired wire (eliminates loop antennas by cancelling magnetic field due to the loop formed by each wire)

·         Shielding components and wires

·         Ferrite beads for high frequency noise suppression

Real estate was another constraint in this design, since it is a small robot. Therefore, use of ferrite bead was not ideal for surface mount components, such as the switching voltage regulators. However, the use of ferrite beads on the brushed DC motor terminals is possible. The effect of shielding in this robot is not much effective either. The best way to make sure there will be minimal EMI in the final robot is the placement of the components according to their type and using bypass capacitors. All the digital electronics were placed toward the front of the robot, away from motors, switching voltage regulators, and inductors. The only digital component that was placed near the back of the robot is the quadrature encoders, since they needed to be mounted right into the wheel shaft. All the analog electronics were placed toward the rear of the robot.

The size of magnetic field depends on the rate of changes in current. Since the components required very low (in the order of milliamps) current, the effects of magnetic fields due to the inductors are also negligible in this design.

Software Design

The software design portion of the project is responsible for processing raw data from various sensors (i.e. IR sensors) and feedback controllers (i.e. Quadrature Encoders). In a broad spectrum, the software design portion of the project is also responsible for using the processed data to solve the maze.

Range Determination and Path Finding

A combination of six infra-red sensors was used for the robot’s guidance system. Each sensor consisted of one infra-red led and one phototransistor package one on the top of the other. When the left and right wall sensors are within 2” of a wall the analog voltage that is read on those two sensors will be approximately 2.74V for the left and 3.19V for the right.  Due to the width of the cell being 7” and the robot’s width being 3” that gives a clearance of only 2” to detect a wall on either side of the robot.  If the sensors read higher than 2”, then that means no wall is present.  The maximum range of the sensors was around 7”-9”.  For this project the robot only needed to detect objects up to 6”, so the sensors that were chosen were ideal.

Robot Mobility and Speed Control

The Robot Mobility and Speed Control subsystem is responsible for controlling the robot behavior. It is responsible for creating a software interface to be used by the Machine Learning and Mice Algorithm subsystem. This low-level software provides functions for controlling the RPM of each of the wheels. This low-level software also provides processed raw data from the quadrature wheel encoders.  

Machine Learning and Mice Algorithm

"A computer program is said to learn from experience E with respect to some class of tasks T and performance measure P, if its performance at tasks in T, as measured by P, improves with experience E" [2]. The study of machine learning is a branch of artificial intelligence which is concerned with the development of algorithms that take as input empirical data, such as that from sensors or databases. The algorithm is designed to (a) identify (i.e., quantify) complex relationships thought to be features of the underlying mechanism that generated the data, and (b) employ these identified patterns to make predictions based on new data. Data can be seen as instances of the possible relations between observed variables; the algorithm acts as a machine learner which studies a portion of the observed data (called examples of the data or training data) to capture characteristics of interest of the data's unknown underlying probability distribution, and employs the knowledge it has learned to make intelligent decisions based on new input data. [1]. One fundamental difficulty is that the set of all possible behaviors given all possible inputs is (in most cases of practical interest) too large to be included in the set of observed examples. Hence the learner must generalize from the given examples in order to produce a useful output from new data inputs [1].

            For the micro mouse robot this concept was utilized completely.  The sensors would sense a wall and store the value into the maze wall detection array. Depending on the voltage of each sensor would accurately determine how far the robot was from the wall.  Based on values ranging from 0 to 5 volts, the sensors would output an analog input to the microcontroller.  Then the microcontroller would have to convert the analog voltage into a digital voltage for later use.  Utilizing the high-speed 10-bit analog-to-digital conversion (ADC) the DISPIC33EP512MC806 that can handle 1.1 Msps was very effective to determine where the walls were in the maze as the robot moved along.

            Generalization in this context is the ability of an algorithm to perform accurately on new, unseen examples after having trained on a learning data set. The core objective of a learner is to generalize from its experience [3]. Some machine learning systems attempt to eliminate the need for human intuition in data analysis, while others adopt a collaborative approach between human and machine. Human intuition cannot, however, be entirely eliminated, since the system's designer must specify how the data is to be represented and what mechanisms will be used to search for a characterization of the data.

Study and Path Find Mode

The first mode of operation for the micro mouse robot is to study and undergo path finding for the maze.  During operation of this mode the robot has 2 major tasks, learn the entire maze and figure out the quickest path to the goal.  In order to achieve these goals the robot must use the flood fill algorithm.  When the algorithm is first used in this mode it only knows of two conditions which are the start and end locations of the maze.  Then the robot will have a good idea where it needs to go in the maze to get to the end.  However, the only walls the robot knows about are the surrounding 4 walls of the maze.  In order for the robot to learn more of the maze, the robot must travel around the maze and record when it interacts with a wall.  To accomplish this task the robot utilizes the infra-red sensor array.  Only when the side sensors are 2” or less from a wall will it record that a wall is there.  The front sensors will only record walls when the distance is 1” or less away from the wall.  When that happens the robot will not only record that a wall is there and store it into the maze array, but it will also re-calculate the maze and adjust itself to the quickest route to the end.  During basic wall recording the robot will operate on the three modified conditions of the flood fill algorithm.

The Flood Fill algorithm assigns values to each other cells in the maze where these values represent the distance from any cell on the maze to the finish line or destination cell.  For the destination cell, it is assigned the number 0 and each adjacent cell outwards is incremented by one.  An example of a 5x5 maze is shown below, assuming that the robot cannot move diagonally.

In order to calculate the number of total cell values needed for your robot is all dependent on the number of rows and columns.  For instance the maze that was used in this project was 3 rows by 6 columns which would equal 18 total cell values.  Therefore you would need 18bytes to store the distances values for a complete maze. As for a regulation sized maze which has 16 rows and 16 columns would require 256 bytes of memory to the store the distance values. So in total it will require 512 bytes of RAM to implement the routine.  One 256 byte array for the distance values and one 256 array to the store the mapping of the walls.

During this mode of operation the robot must follow these strict guidelines:

After completion of this process map, the program then pulls all of the cells from the stack which empties it and then sorts the cells to determine which has the lowest distance value.

While the robot abides by these rules it will find the end of the maze, but real mazes have walls and these walls wil affect the distance values in the maze.  There are 16 bits in the byte for a cell.  A typical cell byte could look somethinkg like this:

Every interior wall is shared by two cells, so upon updating the wall value for one cell you can update the wall value for its neighbor as well.

Now the robot has a way of recording whether or not it comes into contact with a wall as it moves throughout the maze.  Now we need a way of updating the distance values as the cells are affected.  Our mouse encounters a new wall shown below.

The two directions the robot can travel are north and south while the east and west directions are impossible due to walls being there.  Unfortunately going in those directions would have us go up in the distance value which is unacceptable.  So the robot must update and re-flood the maze with the new distance values.

Suppose that the robot was able to detect every wall in the maze.  The service routine would start by setting the array holding the distance values and would assign the target cell to be 0 shown below:

After the destination cell is assigned a value the rest of the cell are filled in with numbers incremented by 1 from the neighboring cell show below:

A sample pseudo code example is illustrated below depicting the flooding of the maze:

·         Let variable Level = 0

·         Initialize the array Distance Value so that all values equal the max (for example 255 for a 16x16 grid).

·         Place the destination cell in an array called Current Level

·         Initialize a second array called Next Level

o   Loop until Current Level is empty

o   Remove a cell from Current Level

o   If Distance Value(cell) = 255 then

§  Let Distance Value(cell) = Level and place all open neighbors of the cell into Next Level

o   End if

·         The array Current Level is now empty

·         Is the array Next Level empty

·         If no do the following

o   Level = Level + 1

o   Let current Level = Next Level

o   Initialize Next Level

o   Go back to “Loop”

·         If yes maze is done flooding

Following is a synopsis of the search mode operation.

7.2.3.2. Execute Mode

The last mode of operation for the micro mouse robot is to find the quickest route throughout the maze.  In order to achieve that the robot must collect the data that it found in the first mode of operation and run the flood fill algorithm to determine the quickest route.  Upon reaching the destination cell, the robot will travel from the current position back to start. During that time the robot will determine the quickest route back to start based on what it has discovered. Upon arrival at the starting point the robot will await a command by switching the switch to the next mode.  When the switch is flipped the robot will run the flood fill algorithm one last time and proceed towards the destination cell.  During this mode the robot will try and maximize speed traveling through the maze since it already knows the way to the end.  There will be no stopping for recalculation in this mode, just straight up pedal to the metal to the end of the maze.  When the robot reaches the destination the robot will turn around and go back to the starting cell and will wait for more instructions traveling in the same path it had come from.  Turning the other switch will power down the robot and flash the memory of the robot, basically giving the robot a new clean slate for learning a different maze.

Following is an overview of the entire software design:

TEST RESULTS AND DISCUSSION

Prior to assembly of the robots, the components went through simple preliminary test to make sure that each component performs according to their description. Once the robot was assembled, it went through a much more rigorous test. Each of the subsystem of the robot was tested to make sure they perform as designed.

The Power Management subsystem was the very first thing that went through a series of test. It is indeed the most important part of the project. If the Power Management subsystem does not provide adequate power at a rated voltage and current, none of the subsystems will perform as desired. Once the robot was turned ON, potential drops on critical part of the robot was measured. Fortunately, the Power Management subsystem passed its test by providing 3.3V and 5V potentials to their respective components.

Afterward, the Control System and Vehicle Dynamics subsystem went through some test to prove its performance. When power is provided directly to the motors, the wheels spin normally. While the wheels spin, the readings from encoder outputs were also measured using a digital millimeter. When the robot was being controlled by the DSC, the quadrature encoder output readings fluctuated between 0V and approximately 5V as expected. The Control System and Vehicle Dynamics subsystem also passed its test. Following images from oscilloscope proves the reliable performance of the quadrature encoders under normal operation.

After the previous subsystems passed their test, the Obstacle Avoidance and Path Finding subsystem went through its series of test. This subsystem used the IR sensors as its primary hardware. This IR sensor array that was used contains 6 IR sensors in an array. Therefore, it was necessary to calibrate the individual sensors. Not all the sensors were consistent upon different scenarios. However, the standard deviation in data among the different sensors can be compensated in software calibration. Mathematical models and functions can be developed using Microsoft Excel to perform accurate calibration. Following are the test results for IR sensors when tested with white paper and wood.

Once each of the hardware subsystems passed their test, it was time to make sure the dsPIC33EP512MC806 digital signal controller (DSC) can be programmed. First the team needed to learn the syntax and study the hardware file of the DSC. Once the team developed some knowledge to program the DSC, the PIC Kit 3 was connected from the computer USB 2.0 port to the DSC programming pins that were designed and implemented on the robot. At first the PIK Kit 3 failed to receive a valid device ID from the DSC. However, after some debugging with the software, the PIC Kit 3 started to receive valid device ID from the DSC. This made sure the DSC programming pins on robot are properly routed to correct DSC pins on the dsPIC33EP512MC806 and the DSC is receiving its required operating voltage and current.