Path Planning – Wavefront algorithm

REPORT 4

Introduction:

One of the main achievements for functioning robots is to perform interesting tasks on its own. Some robots have been programmed to fold napkins; others have been able to help assemble various car parts, and recently, NASA launched their newest rover, Curiosity, to Mars on an exciting exploration mission, to tell whether there could be life on Mars and so on. The world of robotics seems to get bigger and interesting each day and this is as a result of the different components and studies that come together to make robotics what it is today. One of the studies is motion planning, and in this report we will discuss one of the various motion planning algorithms – Wavefront algorithm – and relate it to a particular task that was given to us in class.

Task 4: Application of Wavefront Algorithm:

In the task that was given, our goal was to program a robot to find its way from a starting point to a goal area given a map. In this map, obstacles are placed in various points and the robot must prevent itself from crossing any path that had an obstacle in the way. In other words, the robot must find an optimal path from the starting point to the goal point without moving into the path of obstacles.    The map is represented in a 2D array with a starting point (x and y coordinates), which has been defined already for us. Below is a simple file demonstrating the map

 

#define X_SIZE 5

#define Y_SIZE 4

#define MAP_AREA 20

#define FREE 0

#define OBST 1

#define GOAL 2

 

int world_map[] = {{0, 0, 0, 0, 0},

{0, 0, 1, 1, 0},

{0, 0, 1, 0, 0},

{0, 1, 0, 0, 0}};

int start_x = 1;

int start_y = 2;

int goal_x = 4;

int goal_y = 3;

 

The world_map[] is  a representation of a given area in which the robot can traverse and below is the declaration of the coordinates of the start position and goal position in the map.

Implementation and Observation:

Path Following:

We divided the task into two major models. The first part was to plan a path for the robot(path following) to follow in a given map. Before we were able to complete this model, we created different methods for specific tasks. Some of the methods are spinLeft(), spinRight(), moveForward(), moveBackward(). As the names of the methods suggest, they perform exactly the task given it. Also, we implemented another method known as orientation() and direction(). The orientation method defines the robot’s position at a given time in a particular cell. So the robot could be facing north, south, east or west depending on the direction it is heading. Now this takes us to the direction method. The direction method only helps the robot to move into the next cell after processing all its neighbouring cells. So we had four different direction points labeled 1, 2, 3, and 4 and at every orientation the robot must determine which direction it is heading with respect to the cell it must move to.

Wavefront algorithm:

The next model was the application of the wavefront algorithm. This time the robot wasn’t given a path to follow but was given a map, a starting point, a goal point and obstacle cells. The work of the robot was to apply the wavefront algorithm to the map, extract the path from the map and follow the extracted map.

Implementing:

We were required to repeatedly process cells and this was done by implementing queues to store the cells. Now we had to add elements to the queue and so we added the goal cell to the queue. As long as the queue is not empty and the start cell has not been processed, and this is done over and over so far as a cell hasn’t been processed. Then we take the next cell from the queue, set their values by adding one (1) of the current cell.

Observation:

We faced series of challenges when implementing the wavefront algorithm. One major challenge was that whenever the robot made a right turn or a left turn, it couldn’t determine its direction as defined earlier in the report. Another was how to extract the path after the robot has gone through the map. Also, we experienced oscillation between two cells, in other words, when the robot was going to make a left turn or right turn, the robot keeps going back and forth between its current cell and initial cell.

Conclusion:

This task gave us a real experience in motion planning, and made us understand the various principles that come together to complete this task with respect to wavefront planning.

 

Keith and Frank

BUILDING A SIMPLE MACHINE FROM LOCAL MATERIALS

Edem Adzo Diaba

Frank Anamuah-Koufie

REPORT ON TASK 1

Introduction

The objective of the task was design a system of machines capable of moving a small ball (6cm diameter) across a distance of one metre into a goal area. The goal area has dimensions 25cm X 25cm X 10cm. the mechanism is designed to be touched once and be “automated” for the rest of its course.

Design

The following constraints affected the design of the machine:

1. The machine must be composed of locally acquired materials only.
2. Materials purchased in building the machine should not cost more than GHC20.00.
3. The machine must be composed of a minimum of four simple machines.
4. The machine may only be touched once, the purpose of which is to get it started.

The constraints listed above naturally limited the options we had in designing a solution. However, it also paved way for creativity and new thoughts about possible uses of some materials that were considered to be waste materials or would have never been considered in the building of mechanical systems.

Concept

We pictured the machine in terms of the stages involved in accomplishing the task. These were:

1. Picking up the ball
2. Moving the ball across the distance
3. Dropping the ball in the goal area

In picking up the ball, we considered several options that included having an arm attach a metallic tape to the ball and picking the ball up with an attached magnet. We also came up with a “dustpan and broom” mechanism that would “sweep” the ball from the floor unto a “launch pad”.

 We considered three possibilities for moving the ball across the distance. The first option was to “fly” the ball using a catapult or lever mechanism from the machine directly into the box. The second consideration involved rolling the ball on the ground from an inclined plane straight into the box. But this was based on a misconceived idea that the goal area would have a front-facing opening rather than the upward-facing opening it had. Our final consideration was to have the ball drop from a height and then bounce into the box in a calculated number steps.

One option for dropping the ball required actively dropping the ball into the goal area by turning of an electromagnet that would be mounted on an arm carrying the ball across. The other options were simply passive results of the “moving process” and as such would not require a deliberate attempt to drop the ball.

Each of the three steps were tested independently to ascertain their efficacy before being tested together to see how the whole system may work.

Implementation

We chose to use an iterative process in building the machine. The steps involved were designing, building and testing in that cycle respectively. We began with 2 days of brainstorming and sketching our initial ideas on paper. At this stage, we considered no physical limitations and allowed all sorts of ideas to flow.

The next step, which involved building models, was more realistic. At this stage, we focused more on the physical challenges that the machine may face. We considered weight limitations, material limitations and the role certain forces such as gravity and friction would play on the functioning of our machine.

Our first model involved 3 simple machines; a pulley to release a calculated weight onto an inclined plane. The weight would then slide down the plane and gather momentum enough to catapult the ball from one end of a simple lever into the goal area.

Our tests revealed a number of challenges and provided some new insights into building the machine. We realized that using a stone as our weight was difficult because we could not control the weight and it was also difficult to get the ball rolling on the inclined plane. Another challenge we encountered was getting the pulley to support two heavy stones. Theoretically, we thought the two would balance themselves but in reality, they put a lot of strain on the pulley and almost split the wooden support.

After several iterations, we finally came up with a design that was composed of three simple machines, not meeting all the basic requirements of the challenge. The final machine instead of having one human intervention point had two. The final design was composed of two inclined planes and a lever. The lever and inclined plane we put together using pieces of wood. We used a sock filled with sand as the weight in place of a stone because it was easier to adjust the weight. The mechanism employs four energy transfers:

1. At one end of the machine, a rubber band holds the weight in place and a wedge holds the ball at another end.
2. The rubber band is released and at that instant, the wedge is turned.
3. The ball and weight move down the two planes with the ball arriving on the “launchpad” first. This is because the ball is lighter and moves on a shorter inclined plane.
4. The weight, which is a sock loaded with sand is much heavier and on a longer plane so arrives later at the other end of the lever.
5. The weight lands on one end of the lever and shoots the ball into the box.

Materials Used

1. Plywood – for inclined planes and lever
2. Sand – Weight
3. Sock – Container for weight
4. Rubber band – Trigger
5. Nails and kebab sticks – for nailing components together.

Conclusion

This task has opened our minds to new ways of thinking about some of the local materials scattered around us. It has also shown us how some ideas may look very simple on paper but can be gruesomely difficult to build in the real world. It is indeed a perfect introductory work to a class in robotics as it has made us appreciate the importance of robots in our activities.

 

 

MULTI-ROBOT COORDINATION ( FINAL PROJECT)

FRANK ANAMUAH-KOUFIE

ROBOTICS

DR. AYORKOR KORSAH

21^ST DECEMBER, 2012

FINAL PROJECT REPORT

 

INTRODUCTION

The objective of my final project was to probe further into the subject of robot communication and coordination. I wanted to gain a better understanding of how multiple robots are able to share information and collaborate on tasks in real time. Initially, I planned to design a system of robots with different capabilities that could determine how to collaborate and perform given tasks. However, I settled on implementing a system of similarly-designed robots that will collaborate on a specific task. For my final demonstration, I designed two robots that would simultaneously carry a box along a path. One of the robots would act as the master and will send driving instructions to the second robot. The second robot, the slave, would simply follow the instructions of the master.

APPROACH

After carefully thinking through the project, I divided it into three sub tasks – the robot design, communication mechanism and carrying of the payload.

 

ROBOT DESIGN

 I began by researching on NXT robot designs that could perform the task of carrying the box. After several considerations I decided to build forklift robots so that they could carry the payload off the ground. I did not readily find a design that had the forklifts on the side so I designed one myself. The robot employed a two-wheel differential drive system with a motor to power each wheel and a castor wheel at the back. It also had a third motor that powered the forklift. The design of the forklifts resulted in one side of the robot being heavier than the other which caused some irregular driving behaviour. However, I fixed this by determining the ratio of imbalance and configured the nSynchedMotors function accordingly. I carried out a number of tests to ensure that the forklifts would be strong enough to carry the box.

BLUETOOTH COMMUNICATION

The next objective was to create a reliable communication mechanism between the robots. I tested out the Bluetooth functions available for NXT and realised that a lot of them were not applicable for my purposes. I ran into several difficulties at this stage of the project and had to spend a considerable amount of time resolving them. The major challenges were maintaining the connection between the robots as the robots kept losing connection on several occasions and also problems with delays in message sending. I overcame these challenges by repeating some activities to ensure increase the chance of success and also increased the amount of time scheduled for some Bluetooth-related processes. Also, by running repeated tests I managed to figure out the average time it took activities such as Bluetooth search and message sending to occur and used that as the wait time for those processes. The results of these were greater reliability and a stronger communication framework between the two robots.

CARRYING THE BOX

The challenge in accomplishing this task was to develop an algorithm that would calculate the required motor power and duration needed by each of the four motors. This drew from principles of inverse kinematics where I knew the desired robot configuration and so had to determine the configuration of the individual wheels. I carried out a number of tests to determine the motor requirements for the robots individually and recorded the results. I used this data to determine the relation between the motor powers and durations of the two robots. I used this approach in developing the synchronized movement algorithm because working with angles did not produce desired results. This was due to the fact that the motor encoders took their recordings in degrees of rotation rather than provide angular values. I tested the function several times as well and fine-tuned the time requirements to achieve near perfect synchronisation.

RESULT

Putting everything together for the first time gave me heartbreak as the entire system broke down. Connection and message-sending began to fail and in effect the robots were unable to even lift the box together. A lot of it was due to the fact that it was the first time I had put everything together and had not taken a lot of factors into consideration. I had not provided any fall-backs in case communication delays were experienced and I had not accounted for natural discords in motor coordination. However, with a good number of tests and redesign, I managed to get the system to function together correctly as planned.

CONCLUSION

In doing this project I have learnt a lot about robot coordination and communication. I have seen first-hand the problems that face this field of research chief among which are communication failures. However, I managed to have a successful implementation which shows the immense opportunities that exist in the real world for such systems. It is possible to design systems that will have planet exploration robots or rescue robots share resources and join forces to carry objects or accident victims so that no particular robot is overloaded.

 

Exploration Robot (Robotics Final Project)

Daniel Botchway

Final Project Report Document

Introduction to Robotics

Dr. Ayorkor Korsah

21^st December, 2012

Introduction

The overall concept of my final robotics project was to design and build an exploration robot that would scan its environment and build a map that accurately represents that environment. In the project proposal submitted, the focus of the project was on motion planning and mapping using the Histogramic In-Motion Mapping (HIMM) technique. However, this algorithm could not be implemented but rather a solution I developed based on my understanding of the concept of the HIMM technique and the CMU mapping technique from which the HIMM was developed from.

The motivation behind this project was the interest I got from reading about robot mapping and motion planning. Deeply thinking about the HIMM and SLAM (Simultaneous Localization And Mapping) techniques was thrilling especially comparing it to how easy it is for humans to get the sense of their environment and simply know where they are and move around flawlessly. Unlike the excitement from reading, actually executing this project was awesomely tedious.

Design Concept

The initial designs of the project after a few brainstorming sessions before drawing up the project proposal got outrageously out of scope with the concepts of autonomous localization of the robot. This idea just like the implementation of the actual HIMM technique required the whole project to accommodate a certain level of randomness and unpredictability that would make the project difficult to complete considering the limited time frame.

A more simple design concept was developed to eliminate the element of randomness and unpredictability. The design was

1. To move in a calculated manner of one cell at a time using 8 point connectivity on an occupancy grid map.
2. To scan the four main sides of the robot.
3. To use a mathematical model to generate the senor output into information for the map.
4. To visit every cell in the grid to generate the map representation.
5. To send the map data from the robot to a remote site for visualization.

Implementation

Movement

Building off from the designs used in the Wave Front planning task, the fundamental code for moving to a series of cells making a path was already available (i.e. the Movement module). This module had functions for moving one cell forward, turning 45 and 90 degree right and left, determining the bearing of valid neighboring cells and moving appropriately to them.

Architecture

Also, the same robot architecture was used with slight modifications to accommodate the four sonar sensors. The sensors were placed in front, behind, on the left and on the right sides of the robot as illustrated in Figure 1. The positioning of the sensors gave a fairly complete view of the area around the robot though not a complete 360 degree panoramic view.

Figure 1

Coverage

The next critical and ultimately the most challenging task was to develop a coverage algorithm that would allow the robot visit every cell in a given grid. I spent a lot of time searching for ideas and already existing algorithms that insured that every cell in a grid would be accurately covered in the most efficient manner. Most of the results of my search pulled up concepts that had to do with graphs like the Travelling Salesman Algorithm and other Graph Coverage Algorithms.  Despite that, already existing implementations of these algorithms that suited the project I was working on proved futile. These algorithms did not use the idea of moving systematically from one cell to the other using only valid neighbor cells available but rather computing a path using a Bresenham’s line generation algorithm from a current cell to the next optimal cell in the coverage sequence. Also, the graph coverage algorithms did not accommodate the presence of dynamic obstacles present in the environment.

After, several attempts of designing, testing and redesigning of a model that would allow the robot efficiently cover every cell in a given grid while accommodating the presence or absence of obstacles, a solution was finally developed (i.e. the Path Module). The fundamental theory of this Path Module is

1. To start at a given known location.
2. Find all the valid neighboring cell of the current location i.e. cells that have not been visited, cells that have no obstacles and cells that are not outside the defined area of the map.
3. Move to the first valid neighboring cell.
4. Store all the valid neighbor cells that were not chosen into an unvisited cell data structure variable.
5. Remove current cell from the list of unvisited cells.
6. If no valid neighbors are found and the size of unvisited cell data structure variable is not empty, then backtrack to the most recent unvisited cell using a Wave Front planning algorithm that re-plans after every move to a destination cell.
7. When all the unvisited cells have been visited, terminate the process.

This module was developed from scratch from simply experimenting with ideas that came up and fixing faults that arose from testing those ideas. Major fault encountered when developing the coverage algorithm was determining when to stop after every cell was covered without moving back and forth between two cells infinitely. Prior to using the Wave Front backtrack idea, the algorithm run over a 100 time in order to cover just a 5×5 grid map. This was because, the back track idea used then, was to keep track of all the covered cells and undo each move (by going back the path covered)  until an unvisited neighbor cell is found. Because, the earlier algorithm retracted along the path already covered, when an obstacle gets in the way of the old path the algorithm failed.  The Wave Front plan and re-planning backtracking concept catered from new obstacles that blocked already covered paths and provided options no matter the situation.

Map building

The next sub task was to translate the senor readings into a mathematical function that would be used in building the map. The approach used in the HIMM algorithm was understandable in theory but difficult in implementing. In this area also, I experimented with idea and the failures they brought up until a Scan and Map Building Module was developed. The theory underpinning this module was as follows;

1. Take sonar readings from the four sensors (an average of 10 readings was always taken to make up for the noise encountered with the sensors).
2. The readings are then converted into the grid cell range values by dividing the readings by the length of one grid cell. This meant that every obstacle was known not just by the distance in centimeter but also by the number of cells away.

i.e. So an obstacle that is detected 100cm away has a grid cell range value of 100/ 45 = 2.222, which is about 2 cells away

1. With the grid cell range value and the current bearing of the robot (i.e. North, South, East or West) the appropriate immediate four neighboring cells (because only four sensors were mounted) of the current location were updated to the grid cell range values. As illustrated in Figure 2 and 3, the four neighbors of the current location are updated with values that represent the number of cells between an obstacle and the current location cell. When the robot moves to the next cell, the same procedure is repeated as shown in Figure 4 and 5 and Figure 6 and 7.
2. The current cell is given a value of 7 to indicate that it is certainly free. A cell with a value of 7 cannot be re-updated except on the event when the grid cell value of that cell is determined to be 1 (i.e. certainly occupied) in building process.
3. Continuously updating the four neighboring cells of each grid cell builds a map that adequately represents the environment. This technique also captures changes to the obstacle present or absent in the environment without erratically changing certainly free cells.

Communication

The next sub task of the project was to work on communicating with the remote Bluetooth server. I downloaded source code that implemented a java Bluetooth server from (http://www.miniware.net/mobile/articles/viewarticle.php?id=22).  After studying the RobotC API and experimenting with the ideas used by other RobotC NXT Bluetooth communication projects online, a communication module was developed. This module did the following things;

1. Turn on the Bluetooth functionality of the robot.
2. Set the robot Bluetooth visibility feature to discoverable.
3. Search for and pair with my laptop on port 2.
4. Activate the communication stream to write raw bytes of data.
5. Shutdown the Bluetooth server after completion.

The robot after establishing communication with the Bluetooth server sends initial data that is used to initialize certain parameters on the server side. The robot then sends frequent data updates about its current position in the map, its bearing and the latest version of the map being developed.

On the server side, the data packets are identified and approximately represented in text on the console display. Also, a color coded interface of the grid displays the information being sent from the robot for better visualization. This visual component was developed from java applet code used by Programming II student in one of their assignment. As illustrated in Figure 8, cells with the value of 0 are unexplored and have a gray color, cells with the value of 7 are certainly free and have the color green, cells with the value of 1 are certainly occupied and have the color red, the current cell location is color coded yellow while any other value between 2 and 6 have the color blue and are in the known unvisited cell list.

Discussion

It is critical to point out that, I did not fully understanding the implementation of the HIMM technique I studied. The algorithms I developed were mostly my own understanding of the concepts presented in the readings and research I had done. After several test runs of the whole project, I realized that the robot constantly lost it sense of location whenever the emergency obstacle avoidance module was triggered in.

The robot used the generated map to avoid obstacles and the Wave Front planning algorithm allowed it capture changing obstacles very well. However, in case the robot detects an obstacle in a 10cm range in its path that was not initially detected before it starts moving, an emergency avoidance module is triggered to take it back to the cell it was moving from. Triggering this module repeatedly causes the robot to lose track of its current location in the map. The cause of this malfunction is still not known and thus has not being fixed.

One other major challenge encountered was actually getting already existing implementation of the various concepts that were described in the papers I read. Sample code or pseudo code of how the techniques presented in the research papers could be implemented, were not available to serve as a guide for the work I was doing. This is the main reason I moved towards implementing my own understanding of the concepts they presented.

Conclusion

In conclusion, I would say this was a very exciting challenge for me and I really got to appreciate the technical and mathematical skills needed to develop a fully functioning robotic project. Unlike programming where debugging only occurs in the code; with robotic projects, bugs could arise from mechanical faults when building the robot with the Lego kit, electronic faults from the sensors or NXT console, logical errors from the concept of the algorithm being implemented or syntax errors from the very limited RobotC language.

Despite the satisfaction from getting the robot to work, I was really excited about the fact that I designed and implemented my own algorithms that work quite well and that I could to a large extent predict every move of the robot. The ability to predict gave this feeling of control and help me really appreciate how complicated yet beautiful the human mind is. I believe, this was a successful job done and I am excited about taking on the next challenge of mapping the whole Ashesi University campus in my final year capstone project using the KINECT kit and the Roomba Robotic kit.

Final Project: Planning in Dynamic Environment

INTRODUCTION

The objective of my final project was to program an NXT mindstorm robot to move in a dynamic environment, an environment where the positions of obstacles are unknown. The algorithm I decided to use in order to achieve my goal is the D* Lite algorithm, a rapid re-planning algorithm coined by Sven Koenig and Maxim Likhachev. The main tasks in the project were as follows:

• Implementing the D* Lite algorithm
• Detecting of obstacles
• Moving from a start to goal location given a planned path

APPROACH

The D* Lite algorithm is implemented using a priority queue. The first step in this project was to implement a priority queue. I implemented the priority queue by transposing an implementation done in Java by Mark Allen Weiss into Robot C. Upon implementing the priority queue, the next step was to start working on the D* Lite algorithm, the main part of project.

The D* Lite algorithm is made up of four main modules: CalculateKeys, UpdateVertex, Initialize, ComputeShortestPath and Main.

State: In my project, a state is used to describe  a cell in the world. It consists of the x and y positions of the cell in the world map, the g value, rhs value and the keys.

Initialize(): this module initializes the search problem before the shortest path can be computed.

CalculateKeys(): calculates the two keys of a state. The first key determines the position of a state in the priority queue. The second key is used to determine the position of a state on the priority queue when the first keys of two states are the same.

UpdateVertex(): this module updates the rhs-values and keys of the vertices potentially affected by the changed edge costs as well as their position in the priority queue

Main(): the module is the main part of the project and puts together all the other modules.

D* LITE ALGORITHM

The D* Lite algorithm focuses on identifying cells efficiently to be processed. Consider a robot with a goal location in an unknown terrain.  In moving from cell to cell to arrive at the goal location, the robot uses eight-point connectivity and moves to one of the eight cells with the least cost. The robot calculates the shortest path from its current cell to the goal cell under the assumption that cells with unknown blockage status are traversable. The planned path is then followed to the goal cell if no untraversable cell is observed. If a cell is untraversable, the shortest path is re-computed from the robot’s current location to the goal location.  The goal distances, distance from the cell to the goal, of all cells are important since one can easily determine a shortest path from its current cell of the robot to the goal cell by greedily decreasing the goal distances once the goal distances have been computed. The goal distances of cells change as untraversable cells are detected. The number of cells whose goal distances change are minimal and are sometimes irrelevant in the calculation of the shortest distance. Therefore, in order to efficiently calculate the shortest path, one must efficiently identify the relevant cells. Therefore the D* Lite algorithm solves this challenge.

 

RESULTS

Implementing the D* Lite algorithm which is the core part of the project was challenging but to successfully complete the project, I implemented each of the modules and ensured that each was working correctly. In piecing together the entire algorithm, I encountered various issues which I did not consider during implementation of the modules. I had to make sure that in getting the numbers of each cell to be processed I had to ensure that they were within the world map and not outside the boundaries. I first implemented the algorithm to work in static environment and made sure that path extraction and movement was working perfectly. The next step was to integrate obstacle detection into the project in order to achieve the objective of the project. To achieve this I used code written by Daniel Botchway 2013 Computer Science, my colleague in the robotics class. These methods detected obstacles and updated the world map working with the sonar sensor. In the world map, one (1) represented obstacle and zero (0) represented a free cell. Upon including these methods and implementing the re-planning section of the D* Lite algorithm, the algorithm worked only if the obstacles were not in close proximity. I therefore had to demo with fewer obstacles than planned and make sure that obstacles were not next to each other. Looking back, I think the problem with the implementation of the algorithm was how I was trying to avoid obstacles. In making the decision on which direction to turn, I never checked the world map to check for obstacles. I believe this omission in addition to the not so perfect implementation of re-planning section of D*Lite algorithm resulted in the robot failing to move and the program unexpectedly closing.

APPENDIX

Figure 1 below shows an example of the world map used in implementing the D* Lite algorithm. The robot moves one cell at a time, checking the next cell for obstacles. Figure 2 shows the D* LIte algorithm as written by Sven Koenig and Maxim Likhachev in the reference paper for this project, D* LIte.

Figure 1: example of world map

Figure 2: D* LIte algorithm as written by Sven Koenig and Maxim Likhachev

Figure 3: Ultrasonic sensor used for obstacle detection

 

Wavefront Planning-Task 4

Task: Path Planning

Group Members:

Flynn Darko

Selase Attah Kwamuar

Lecturer: Dr. Ayorkor Korsah

Task 4 Report

Introduction & Objective

The task required us to implement the wavefront planning algorithm to enable our robot plan its way through a specified map from a start point to a goal area.

Design Concept

The task required us to implement the wavefront algorithm in an enclosed map that was divided into grids and with “x” and “y” coordinates/boundary. The figure below shows the whole map divided into grids. The numbered grids each have an x and y coordinate and contain the numbers 0 and 1 which specify free spaces and obstacles respectively.

Figure 1: Our World Map

As can be seen above figure 1, gives a summary of the task our robot is to perform. The robot is supposed to start at the “start cell” and follow along the red line until it gets to the goal cell or area. In the implementation section of the report, the program is explained further.

The concept we decided to follow is as follows;

• Get specified map
• Populate map from goal area
• Calculate and find shortest path
• Using the shortest, navigate to the goal area

Implementation in RobotC Language

Before going ahead to write the program to implement the wavefront algorithm the pseudo code that follows explains the structure of the our program;

Cell Population

Set value of goal cell to 2

Enqueue goal cell

         While  (start cell has not been processed)

                currentcell = Enqueue

                Expand currentcell

                for each neighbor of currentcell, set neighbor’s value to currentcell value

                Enqueue neighbor

Path Extraction

Start at the start cell

While not at goal cell

                Move to the neighbor cell with the smallest value which is an not obstacle

Navigate to goal Cell

 

Implementation Stages

Movement through the map (tiles)

To do this we had to calculate the distance between the center points of two cells

And write a turnLeft() and turnRight() function for our robot.

Writing a function for the movement of the robot was the first part of the task we implemented. After using and observing how the encoders work and using the distance calculated for the tile distances we implemented forward, left, and right movement of our robot. The respective functions used in our program were moveForward(), ninty_turnLeft() and the ninty_turnRight(). We also had to make sure that for the left and right turns our robot turned 90 degress for both turns. We were able to do this by adjusting the magnitude of the power assigned to the both wheels for the respective turns.

Displaying the map on NXT screen

To implement this we used a printWaveMap( ) method to display the map specified in the planning_map.h source code. Using the nxtDisplayString( ) method we printed the various map values in the various cells, specifying the free cells with 0, obstacles as 1 and the goal cell as 2 as can be seen in figure 2.

figure 2

Populate the cells from the goal area to start area

After implementing the display of the given map on the screen of the robot, we went ahead to populate the cells within the map starting from the goal cell.  That is, the wavefront plan. We used unique functions namely addQueue( ) and removeQueue( ) to queue all the processed cells until we got to the start area. These functions also made use of variables which were passed as parameters in the function to queue up the values of the neighboring cells as they were populated. From figure 3, it can be seen that from the goal area 2, we populate the neighboring cells which are enqueued till we get to 12 which is the start area.

 

figure 3

Planning and Navigating through planned path to goal

Finally, we made use of the movement function and the wavefront plan to implement finding the shortest path and navigation to the goal area. The program algorithm we wrote for this implementation is as follows;

1. Given the start cell of robot
2. Get value of cell
3. Compare value of that cell to its neighboring cells and find the least cell value
4. Repeat steps 1,2 and 3 till it gets to the goal cell which is 2
5. Save shortest path in an Array

After finding the shortest path to the goal we encountered the challenge of factoring in the orientation of the robot. Relative to the bearing of the world map we were using, the orientation for the robot changed after a turn.

We therefore had to use a variable called heading which was assigned variables representing the current bearing of the robot. In our program this enabled us to inform the robot to know the position of the minimum cell to itself and know which direction to turn in order to get to the right neighboring cell with the minimum number.

figure 4

Challenges

On major challenge we faced was how to factor in the orientation for the robot. After getting an understanding of the concept of how to use it, we still had a lot of errors when implementing it in our program. We had to write about sixteen conditions for all possible positions of the minimum cells the robot was supposed to move to and the current orientation for the robot as well. We were however finally able to have our program ran by writing a condition for all four possible orientations for the robot. This included a condition for when the robot was facing north, east, south and west. Each condition included the action the robot was to take depending on where the minimum value cell was to the robot.

During our testing, we also realized that our robot did not exactly turn 90 degrees for both left and right turns. We therefore had to adjust the assigned motor powers as well as the wait times.

Conclusion

After debugging our program following each unit task we realized that our approach to the task cost us a lot of time on the whole task. What we had to do first was implement the movements function and make sure our turns worked before writing our program for the wavefront plan. This would have saved us some time since we had to go back and correct the movement functions.

In summary this task was challenging in terms of determining the orientation of the robot upon every turn but it taught us the value of breaking a problem or a solution algorithm down to the very minute detail since this really helps when writing the program.

Final Project. Building a Sorter Robot

Task: Building a Sorter Robot

Flynn Darko

Lecturer: Dr. Ayorkor Korsah

 

Final Robotics Project

 

Introduction & Objective

The objective of this project was to build and program a robot that would sort a number of maize grains painted in different colors. When the color of the painted grain is detected, the sorter robot places it in the assigned container placed in front of it. The robot is supposed to do this until all the grains are sorted into the respective containers.

 

Design Concept

Structure

My first conception of the how the structure of the sorter robot should be was first influenced by a model I saw online which looked like the one shown in figure 1.   I therefore went ahead to build the model using the building instructions that came with it. However, I had stated in my proposal that I was going to make use of colored maize grains. But looking at the model I had decided on, the grains could not be transported along the inclined structure that this model provided. The model could work well for colored balls which would fall along the inclined Lego brick. Though presented as my first milestone, I decided to work a new model which would be more efficient in transporting the grains during the sorting process. Using a conveyor belt was my next design concept.

figure 1: First sorter robot model

As shown in figure 2, I saw another model which I knew would be the best robot structure model to use. Having no building instructions, I had to build it myself using the various parts from the NXT Mindstorm Lego kit. This took a great deal of the time I had to finish the whole project.

 

figure 2

figure 2

Program Algorithm

During the building process of the sorter robot, I had the following algorithm concept in mind which I wanted to implement

1. Detect and display grain color on NXT screen
2. Upon detection, stop upper conveyor belt and turn lower conveyor belt (upper conveyor and lower conveyor shown as Uconv and  Lconv in figure 3) to the respective bin collector
3. Start upper conveyor again till the grain drops in the collector.
4. Reset lower conveyor to original position
5. Repeat steps I to IV until all the grains placed on the sorter robot are sorter into their respective bins

The next progress was the implementation stage.

figure 3

Implementation

The above figures (figures 2 and 3) show the model of the robot I built. I used a color sensor to help detect the color of the Lego brick color (the colored maize grains were not being detected well by the color sensor so I used Lego bricks instead).  In order to get a conveyor belt I attached a motor to a wheel which had a conveyor belt wrapped around it. This is shown in figure 4.

figure 4

Challenges

As already mentioned, getting the structure of the sorter robot right was the one major challenge I faced. Though I had the program algorithm written down, I could not implement it without building the sorter robot. I was therefore able to implement the program for the sorting process very late to the due date for demonstration. During demonstration, I still had some modifications to make to the rotation of the lower conveyor (Lconv) so that it moved towards the right bin throughout the sorting process.

Conclusion

This final project proved to be very challenging since I had to build the robot from scratch without any building instructions. However, I found it very fulfilling when I was finally able to get it done an implement my program.

Relevance to Problem Solving in Ghana

In Ghana we could have robots that can sort waste to hasten the process of recycling. For example in homes, such robots can be programmed to sort waste materials into labeled bins which would make the reuse of waste possible and much easier.