Code States #3 - Linked Array Based Priority Queue Implementation

Priority Queue

They are the most important aspect, which must be known by any roboticist. Priority queue are used in path planning algorithms in general and shortes path algorithm like Dijkstra's algorithm. There are three types of Priority Queue implementation

1. Using Linked list 
2. Using Linked array representation
3. Priority matrix representation - Space taxing as a lot of elements might be empty

In the next set of Path planning algorithms, I will be making extensive use of Priority Queue. So that we all are on the same page, and you have the prerequisite, I am posting the code for Priority Queue implementation using Linked array representation. Please look into the theory of Priority Queue for implementation of (1) and (2)

DISCLAIMER - 

Though I have taken enough care that no bug is in introduced, I have written it in half an hour. Though I have checked the correctness on run-time, there might be some insidious bug. Please comment them on the blog, so that I can correct them and publish the revised version.

Cheers

Harshal

Edit - The codes below get creepy due to parsing issues that i am yet to figure out. Alternatively, you can fork me on github repository
harpribotics.blogspot
Do Fork me if you like it. :)

//// Array based Priority Queue implementation - Harshal Priyadarshi
#include
#include

using namespace std;
 
void assignRandomLinks(int* link,int* info, int* prn, int & avail, int & start, int size){
 avail = 0;                              //means that avail points to the very first array location
 start = size + 1;                       // means that start does not point anywhere
 
 for(int i = 0; i< size; i++){
  *(link + i) = i+1;
  *(info + i) = 0;
  *(prn + i) = 0;
 }
}
// Note To the readers
// link = size + 1 -> start is not initialized
// link = size     -> that the end point of either the occupied or avail list has reached
void priorityInsert(int *info, int* prn, int* link, int & avail, int & start, int num, int numPr, int size)
{
 //**** search for the suitable place where prn is just greater than numPr. ****\\
 //**** insert the number before that array ****\\
 
 //// check if the queue is full 
 if(avail == size)                       // means that their is no available place
 {
  printf("No place left. Kindly delete some information\n");
  
 }
 else{
 
  //// check if this is the first number to be inserted
  if(start == size + 1) 
  {
   start = avail;
   avail = *(link + avail);
   *(link + start) = size; 
   *(info + start) = num;
   *(prn + start) = numPr;
   
  }
  
  else{
  
   int counter = start;            // initialize the counter to start
   int prevlink = start;
   
   //// run till the pointer is just greater than numPr or till endpoint is reached
   while(numPr >= *(prn + counter) && counter != size)
   {
    prevlink = counter;         // maintains info of before link
    counter = *(link + counter);// maintains info of after link       
   }
   //// this handles all cases 
   int temp2 = *(link + prevlink);
   *(link + prevlink) = avail;     // the before link points to the first available position
   *(info + avail) = num;          // the info of 1st available position is set to num
   *(prn + avail) = numPr;         // the prn of 1st available position is set to numPr
   int temp = *(link + avail);
   *(link + avail) = temp2;        // the avail array points to the after link
   avail = temp;                   // the avail pointer is set to next available location
  }
 }
}

void priorityDelete(int *info, int* prn, int* link, int & avail, int & start,int size )
{
 if(start == size + 1)                   //means that no element was inserted before
 {
  printf("There was no entry in the system. Please feed in values\n");
 }
 else{
  if(*(link + start) == size)         //if the deletion will lead to an empty queue
  {
   int temp = avail;               // the present avail pointer is stored
   avail = start;                  // the start pointer is recovered
   *(info + avail) = 0;            // the values for priority and info is initialized
   *(prn + avail) = 0;   
   *(link + avail) = temp;         // the avail -> next = previous avail
   start = size + 1;               // the start pointer points to some value not representative in the link . We chose (size + 1)
  }
  
  else{
   int temp = avail;               // the present avail pointer is stored
   avail = start;                  // the start pointer is recovered
   *(info + avail) = 0;            // the values for priority and info is initialized
   *(prn + avail) = 0;
   start = *(link + start);   
   *(link + avail) = temp;         // the avail -> next = previous avail
   
  }
 }
}

int main(){
 int size = 10;
 int info[size], prn[size], link[size];
 int * INFO = info;                      // pointer to info
 int * PRN = prn;                        // pointer to priority prn
 int * LINK = link;                      // pointer to link
 int  start;                             // start or head location 
 int  avail;                             // first place available location
 int num = 0;                            // number to insert
 int numPr = 0;                          // priority of number to be inserted
 int choice;                             // choice of deletion or insertion

 //// initialize links randomly and assign the suitable start and avail list
 assignRandomLinks(LINK,INFO,PRN ,avail, start, size);
 
 //// make your choice now
 printf("Press 1 for Priority insert and press 2 for Priority delete ");
 scanf("%d",& choice);
 
 while(num != 99)                        // insert 99 to end the loop
 {                       
  
  if(choice == 1)                     // priority insert
  {                                   
   printf("Insert the number \n");
   cin>>num;
   printf("Insert the priority of number %d \n",num);
   cin>>numPr;
   priorityInsert(INFO, PRN, LINK, avail, start, num, numPr,size);
  }
  
  if(choice == 2)                     // priority delete
  {
   priorityDelete(INFO, PRN, LINK, avail, start, size);
  }
  
  //// print the three arrays
  for(int i = 0; i< size; i++)
  {
   printf("%d %d %d\n",info[i],prn[i],link[i]); 
  }
  
 //// make the choice within the loop
 printf("Press 1 for Priority insert and press 2 for Priority delete ");
 scanf("%d",& choice);
 }
}

Code States # 2 : Breadth First Search Algorithm for Graph

Hello Again!
For those who are not aware of this new series on Code States, in short, here you will get all the relevant codes. It has a two way benefits. I get to keep my codes handy instead of in some misspelled , never to be found folder in some random directory of my system. You get to have the coded implementations of the modules for free. Not everyone wants to do low level coding. They want modules. This will surely help.

See Code States # 1 for Depth First Search Algorithm.

Applications of Breadth First Search:

1. Find the shortest path between two points in a greedy manner in an unweighted graph .
2. To check the number of connected components in a graph.

Some Real world applications:

• GPS Navigation systems: Navigation systems such as the Google Maps, which can give directions to reach from one place to another use BFS. They take your location to be the source node and your destination as the destination node on the graph. (A city can be represented as a graph by taking landmarks as nodes and the roads as the edges that connect the nodes in the graph.) BFS is applied and the shortest route is generated which is used to give directions or real time navigation.
• Computer Networks: Peer to peer (P2P) applications such as the torrent clients need to locate a file that the client (one who wants to download the file) is requesting. This is achieved by applying BFS on the hosts (one who supplies the file) on a network. Your computer is the host and it keeps traversing through the network to find a host for the required file (maybe your favourite movie).
• Facebook: It treats each user profile as a node on the graph and two nodes are said to be connected if they are each other's friends. Infact, apply BFS on the facebook graph and you will find that any two people are connected with each other by atmost five nodes in between. To say, that you can reach any random person in the world by traversing 5 nodes in between. (I did not run BFS on facebook graph, it is a well known fact).What do you think is the new facebook "Graph Search"? (It is not directly BFS, but a lot of modifications over classic graph search algorithms.)
• Web Crawlers: It is quite an interesting application. They can be used to analyze what all sites you can reach by following links randomly on a particular website. 

So have the code and enjoy. See you soon.

Edit ---- The parsing for blogspot is just something i wont appreciate a lot. You can instead find the codes in my github repository. Fork me there, to get the code. The link is just below.
harpribotics.blogspot

# include
# define max_node 50
using namespace std;

struct adjlist{
 int vertex;
 adjlist* next;
};

adjlist *adj[max_node];

int totNodes;

int queue[max_node]; 
int f = -1; // front queue pointer
int r = -1; // rear queue pointer

// to insert in the queue
void q_insert (int item){
 r = r + 1;
 queue[r] = item;
 if(f == -1)
  f = 0;
 
}

// to delete in the queue
int q_delete (){
 int delitem = queue[f];
 if(f == r)
  f = r = -1;
 else
  f = f + 1;
 return(delitem);
}

// to check if the queue is empty
int is_q_empty(){
    if(f==-1)
      return(1);
    else return(0);
}
// creat the adjascency list of the graph

void createGraph(){
 adjlist *newl,*last;
    int neighbours,neighbour_value;
    cout<<"\n\n---Graph Creation---\n\n";
    cout<<"Enter total nodes in graph : ";
    cin>>totNodes;
    for(int i=1;i<=totNodes;i++){
        last=NULL;
        cout<<"\nEnter no. of nodes in the adjacency list of node "< That is Total Neighbours of "<>neighbours;
        for(int j=1;j<=neighbours;j++){
            cout<<"Enter neighbour #"<>neighbour_value;
            newl=new adjlist;
            newl -> vertex = neighbour_value;
            newl -> next = NULL;
            if(adj[i] == NULL){
             adj[i] = newl;
             last = newl;
            }
            else{
             last -> next = newl;
             last = newl;
            }
        }
    }
}

void BFS_traversal(){
    adjlist *tmp;
    int N,v,start_node,status[max_node];//status arr for maintaing status.
 const int ready=1,wait=2,processed=3; //status of node.

    cout<<"Enter starting node : ";
    cin>>start_node;

    //step 1 : Initialize all nodes to ready state.
 for(int i=1;i<=totNodes;i++)
        status[i]=ready;

    //step 2 : put the start node in queue and change status.
    q_insert(start_node); //Put starting node into queue.
    status[start_node]=wait; //change it status to wait state.//step 3 : Repeat until queue is empty.
 while(is_q_empty()!=1){

        //step 4 : Remove the front node N of queue.//process N and change the status of N to//be processed state.
        N = q_delete(); //remove front node of queue.
        status[N]=processed; //status of N to processed.
        cout<<" "<vertex;
            if(status[v]==ready){//check status of N's neighbour.
                q_insert(v); //insert N's neighbour who are in ready state.
                status[v]=wait; //and make their status to wait state.
            }
            tmp=tmp->next;
        }
    }
}

int main(){
    
    cout<<"*****Breadth First Search Traversal*****\n";
    createGraph();
    cout<<"\n===BFS traversal is as under===\n";
    BFS_traversal();
    int n;
    cin>>n;
}

Code States # 1 - Depth First Search (DFS) algorithm for Graph

People get bogged down to writing codes, when all they want is the implementation. Not everyone wants to be a true coder, but wants its benefits. Coding is fun and i suggest all to go this line at some point of their life if not now. This is a new series of blog for those who need reference for various coding algorithm and for those who need all together coding modules. Please feel free to use these codes and distribute it.

This is a code for Depth First Search algorithm for Graph. It is quite an intuitive algorithm and has quite a crisp code. 

Depth First Search algorithm is used in many applications, some of them are as follows:

1. To find if the graph is bipartite or not. A graph is bipartite if it can be divided into two mutually exclusive sets whose union is the set itself, and any edge of the graph joins vertex of one set to that of other.
2. For an unweighted graph, DFS traversal of the graph produces the minimum spanning tree.
3. Detecting cycle in a graph 
   A graph has cycle if and only if we see a back edge during DFS. So we can run DFS for the graph and check for back edges. 
4. Maze Solving - Heard of that famous Mouse and cheese problem on the Maze. We can use DFS for that purpose. It is how we would have done it, if we were a mouse.
5. Path finding - To find a path between two points.

There are many more, but i will give you the chance to Google them yourself. For example, search google for what is a Minimum Spanning Tree (MST).

So here is the code. Enjoy. 

Edit ---- The parsing for blogspot is just something i wont appreciate a lot. You can instead find the codes in my github repository. Fork me there, to get the code. The link is just below.
harpribotics.blogspot
 

# include
# define max_node 50
using namespace std;

struct adjlist{
 int vertex;
 adjlist* next;
};

adjlist *adj[max_node];

int visited[max_node];  // exclusive for recursive DFS

int totNodes;

// creat the adjascency list of the graph

void createGraph(){
 adjlist *newl,*last;
    int neighbours,neighbour_value;
    cout<<"\n\n---Graph Creation---\n\n";
    cout<<"Enter total nodes in graph : ";
    cin>>totNodes;
    for(int i=1;i<=totNodes;i++){
        last=NULL;
        visited[i] = 0; // exclusively for recursive DFS 
        cout<<"\nEnter no. of nodes in the adjacency list of node "< That is Total Neighbours of "<>neighbours;
        for(int j=1;j<=neighbours;j++){
            cout<<"Enter neighbour #"<>neighbour_value;
            newl=new adjlist;
            newl -> vertex = neighbour_value;
            newl -> next = NULL;
            if(adj[i] == NULL){
             adj[i] = newl;
             last = newl;
            }
            else{
             last -> next = newl;
             last = newl;
            }
        }
    }
}
// this quite an intellectual and crisp code instead of the lengthy recursion
void TrueDFS_Traversal(int w){
 visited[w] = 1; cout<<" "<vertex]) TrueDFS_Traversal(adj[w] -> vertex);
 adj[w] = adj[w] -> next;
 } 
}
int main(){
    
    cout<<"*****Depth First Search Traversal*****\n";
    createGraph();
    cout<<"\n===True DFS traversal using recursion is as under==\n";
    // ask for the start node
    int start_node;
    cout<<"Enter starting node : ";
    cin>>start_node;
    TrueDFS_Traversal(start_node);
    int n;
    cin>>n;
}

Sensor Fusion #1 : Alpha Beta Gamma Filter

Sensors are prone to error, no matter how much cash you spend. One way is to spend a lot getting an extremely accurate sensor, while other, more favorable way is to filter out the noise and drift in the faulty reading to get an output as close as possible to the ideal case.

In line with this, let me introduce, the Hello World of Sensor fusion, Alpha Beta Gamma Filter (or Alpha Beta Filter, if not using the acceleration term)

The Alpha Beta Filter is quite an intuitive, yet a very simple concept to begin with. The best explanation that i myself found was on Wikipedia. So instead of delving further explaining the same thing again and again, let me just give you the appropriate link of Alpha Beta Gamma filter from Wikipedia. Please do read it faithfully. It is very insightful and clearly explained.

Algorithm Summary

Initialize.

• Set the initial values of state estimates x and v, using prior information or additional measurements; otherwise, set the initial state values to zero.
• Select values of the alpha and beta correction gains.

Update. Repeat for each time step ΔT:

  Project state estimates x and v.
  Obtain a current measurement of the output value
  Compute the residual r.
  Correct the state estimates.
  Send updated x and optionally v as the filter outputs

Now the major aspect is the implementation. I have implemented the entire filter on C++ with simulated noise and drift. The code is given below. Feel free to copy it and make sure you run it on your platform.

Edit ---- The parsing for blogspot is just something i wont appreciate a lot. You can instead find the codes in my github repository. Fork me there, to get the code. The link is just below.
harpribotics.blogspot
 

/* An alpha beta filter implementation by Harshal Priyadarshi
Blog - http://harpribotics.blogspot.com
*/

#include
#include

10 Newbots - A journey through popular startups

1.  Sphero

GoSphero,Founded by Ian Bernstein and Adam Wilson, passionate robotics and software engineers. They create connected toys, fusing emerging technology with the latest innovations in robotics. You will love Sphero and Ollie.

2. Zeus

AIO Robotics is a fledgling company formed by Jens Windau and Kai Chang that made a prototype of first user friendly 3D printer. They wish to make this as effective as 2D printers,scanners and fax machines. They were graduate students at University of Southern California.

3. 4moms

Mary Koes, Vice President of 4moms was a student at Carnegie Mellon University. This startup is rising to become the leader in the baby products market.

Meet the origami

and don't forget the Mamaroo

4. Rewalk

One of the essential start-ups to the mankind, Rewalk gives the disable all the support it needs. They have worked extensively on exoskeleton.

Argo founder Dr. Amit Goffer was inspired to develop the ReWalk exoskeleton unit because of his own personal story. Dr. Goffer is quadriplegic and he founded Argo in 2001. His goal was to develop a product that would enable persons with spinal cord injuries to walk again. Over the past decade, Argo has grown from a small research and development start-up based in Israel to an international company with headquarters in the US, Germany and Israel.

5. KMEL Robotics

Daniel Mellinger, Co-President and founder of KMEL Robotics was a student at UPenn. His startup on scalable aerial robotics is truely fascinating. See a demonstration below.

6. Ekso Bionics

In line with Rewalk we have a new startup for you. In healthcare, Ekso Bionics (a spin-off from UC Berkeley and 6-year old Berkeley Bionics) and their exoskeleton are beginning to penetrate rehabilitation therapy centers while a 2008 start-up.

7. ROMO

A true product based on Human Robot interaction principle. Be ready to plug and play. 2009 start-up Romotive‘s $149 Romo is selling thousands of their cute little iPhone-carrying devices

8. The Robot Dragonfly

Dr. Jayant Ratti, PhD Robotics and AI from GeorgiaTech, has formed TechJect, one of the most innovative and naturally orineted startup. Rest all lies in the video. So go ahead.

9. QBotix

Wasiq Bokhari, Founder and CEO of QBotix has coupled Robotics with Solar energy. Sounds interesting. Watch this video.

10. Liftlabs

The true innovation for the aged and the diseased. So that they have an equal chance. Have a look.

Do comment if you know about some of the innovative startups out there. Do like and share the post, for others to know about the fact, that it is ideas that make you big.

Localization for Beginners : The key to the AI World

First of all, I apologize for not blogging yesterday. I had been pretty busy with the company placements in my university. I sincerely apologize for not letting you know things.

So, after the apology program is off the memory stack. Let us get to the topic head-on. Localization is a very important concept of Artificial Intelligence. Let us begin with defining this very important term. I shall try to be very informal in my definitions( my sincere apologies to the experts). 

Localization  

Let us begin with blindfolding a robot (I shall call it Blinder). After we have safely kidnapped the robot, next step is to get into a cab and go to a very unfounded place, which the robot is not aware about. Then we remove the blindfold of the so called angry Blinder. We run away, and leave the robot at its own, to search its way out. Now, the primary task of Blinder is to see through its surrounding and find his position and orientation with respect to the surrounding. Quite an easy task, Huh?.

Well true for the humans, but very false for the robots. There are quite many reasons for that . First, it is next to impossible with the present computational resources to program the robot to make sense of all the things around it. What we see as grass, is nothing but a point in the 3D point cloud for the bot. This ability of ours to make sense of our surrounding is called Contextual knowledge in Robotics. The view of Blinder is constrained too. The most sophisticated sensing equipments, like cameras or L.R.F. (Laser Range Finders) are far less sophisticated in comparison to our simple looking EYE. Yes, the most underrepresented entity of mankind is the most sophisticated sensor in the human civilization till date. Thus various locations look quite similar to the robots and thus the probabilistic approach needs to be adopted to differentiate between them. If you are not making much sense out of this, hang On. I will be giving a detailed illustration of all of it.

Probabilistic Approach

Blinder, and all other robots, determines its present position in a probabilistic manner. It creates a map of all the possible positions a robot can be, and then assigns each location a probability. Now initially when the robot's blindfold has just been removed, and it has not grabbed any sensor reading of the surrounding, he/she is totally lost. He can be in any of the N locations possible.

P(i) = 1/N          where,  i = 1 to N

Let us for the sake of simplicity assume that N = 5. To simplify even further, let us assume that robot is lost in 1-Dimensional space. Don't loose heart with such generalization. They scale equally to the actual case of billions of equally likely points located in the 2-D space(the case with Blinder) or in 3-D space (the condition with the manipulators that are free to move in the 3-D space).

Let us make an array of 5 locations represented as boxes shown below, and place a probability of 0.2(1/N(=5)) in each one of them.

  i  = 1          i = 2         i = 3          i = 4        i = 5

0.2

0.2

0.2

0.2

0.2

This plot is also called Belief Space of the robot.

So the robot has no idea as to where he or she is. You might have noticed the color of text in each box. The color of the text is the identity of the box. So there are three blue boxes (i = 1,2,5) and two red boxes(i = 3,4). Each box's color is the only thing which the robot can identify. This is analogous to the identity of each location that the location inherits due to its disparate colors, look, feel etc. For us the robot can't see anything for the unknown locations(boxes) apart from its color. 

Now comes the hard part. To determine the robot motion model. Generally it is Gaussian in nature when the N is pretty large close to millions, which is quite a commonplace case in the Localization world. But that is very complex to express. Let us make it a bit easy, with a Gaussian like model shown below. Let us assume that the robot intends to move only one step forward at a time from one box to the next box. Also, the path is cyclic in order to ensure consistency in such a small work-space. Thus if the robot moves from i = 5 a step forward, then it reaches i = 1.

On the x axis (Tasks)

1 - the robot does not move   

2 - the robot moves the intended one step forward

3 - the robot oversteps and moves two steps instead of one step

On the y axis

1 - Probability of robot to do task 1  = P(1) = 0.2

2 - Probability of robot to do task 2  = P(2) = 0.6

3 - Probability of robot to do task 3  = P(3) = 0.2

Now if we issue a motion command, the probability distribution of the robot changes. This is also called Posterior of the robot motion.

P(i) new = [P(i )old* P(task = 1)  +  P(i - 1)old * P(task = 2)  +  P(i - 2)old * P (task = 3)]

After all the P(i) is updated. Do normalize the Probability to sum to 1.

P(i)new normalized = P(i) new / sum(P(i))

. 

Now a quick question for all you guys?

Q.1) If the robot being at its initial stage intends to move forward, what is the new probability distribution diagram of the robot ?

A.1) At the end of this blog.

Q.2) Let us assume that the robot is initially at i = 2. What is the new posterior provided the robot intends to move 1 step forward.? Assume the motion model as shown above in the blog.

A.2)  

Initial Belief Space

 i  = 1          i = 2         i = 3          i = 4        i = 5

0

1

0

0

0

                                                    Initial Probability distribution Bar plot

Posterior Belief Space

P(1) =  0 * 0.2  +  0 * 0.6  +  0 * 0.2 = 0

P(2) =  1 * 0.2  +  0 * 0.6  +  0 * 0.2 = 0.2

P(3) =  0 * 0.2  +  1 * 0.6  +  0 * 0.2 = 0.6

P(4) =  0 * 0.2  +  0 * 0.6  +  1 * 0.2 = 0.2

P(5) =  0 * 0.2  +  0 * 0.6  +  0 * 0.2 = 0

Posterior

 i  = 1          i = 2         i = 3          i = 4        i = 5

0

0.2

0.6

0.2

0

                                                Posterior Probability distribution bar plot

I leave you to think, that such motion, always deteriorates the accuracy to which the position can be known. Ideally P(i = 3) should have been 1, but due to the inaccurate robot motion and thus a probabilistic motion model, the robot has P(i = 3) = 0.6

Measurement Step

Then we are left with the question as to how to improve the accuracy of the robot motion, or in other words localize the robot in its map. The question might seem tricky, but is very intuitive. We have to measure things to make a more accurate prediction. 

Remember, I marked the boxes with a color that identifies and differentiates one set of boxes from others. This is what the robot will tend to measure. Let us assume that robot has a very restrained vision and can only identify if the location(box) is red or blue.

The robot vision is not accurate either, it is bound to report wrongly. Thus let us maintain a measurement model too. In general we use two coefficients shown below.

Hit Coefficient(HC) = 0.6   

Miss Coefficient (MC) = 0.2

Note : You can choose any two values for the Hit and Miss Coefficients respectively, but make sure that 

HC > MC

Whenever a robot encounters, say a Red box, then it multiplies all the Red boxes in its belief space withe the Hit Coefficient( here = 0.6) , and all the blue boxes with the Miss Coefficient (here = 0.2).

Last but not the least, do not forget to normalize the values of probabilities in the belief space. As sum of these probabilities should always be 1, as the robot can possibly be in only one of these pre defined states. 

So let me throw up a quick question?

Q.2 If initially the robot does not know where he/she is, it moves one step with total certainty (notion model is accurate, i.e robot does not under-step or overstep), and measures Red, then it moves another step with total certainty, and measures a Blue. Please define the new belief space for the robot?

A.2) Hint: the robot motion is totally certain, thus a quick method is to move the belief space terms, cyclically one step forward to get the new motion belief space. 

Step -1 - Motion Step

Step -2 - Measurement Step (Red)

Step -3 - Motion Step

Step -4 - Measurement Step (Blue)

Answer for each of the four steps is given at the end of the blog. Do solve them first, by yourself, before jumping straight to the answer. You will get to have the essence of the Localization. Those who tend to solve this problem, will have the necessary basics to move on in the vast world of Robotics.

Note - You will also observe that Measurement model, increases the accuracy of robot presence in the belief space, while motion model decreases it.

Q. If the above statement in the note is valid, why do we do the motion update, at all?

A. Because, it is the most accurate representation of the robot model. The robot can't be trusted 100% with its motion capabilities. Ensuring a degree of inaccuracy through probabilistic robot models, helps us identify the true robot behavior.

A.1 )

i  = 1          i = 2         i = 3          i = 4        i = 5

0.2

0.2

0.2

0.2

0.2

A.2)Initial

i  = 1          i = 2         i = 3          i = 4        i = 5

0.2

0.2

0.2

0.2

0.2

Step 1 - Motion

i  = 1          i = 2         i = 3          i = 4        i = 5

0.2

0.2

0.2

0.2

0.2

Step 2 - Measurement - Red

i  = 1          i = 2         i = 3          i = 4        i = 5

0.04

0.04

0.12

0.12

0.04

After Normalization

i  = 1          i = 2         i = 3          i = 4        i = 5

1/9

1/9

1/3

1/3

1/9

Step 3 - Motion

i  = 1          i = 2         i = 3          i = 4        i = 5

1/9

1/9

1/9

1/3

1/3

Step 4 - Measurement - Blue

i  = 1          i = 2                i = 3          i = 4        i = 5

0.067

0.067

0.022

0.022

.18

After Normalization

i  = 1          i = 2                       i = 3                     i = 4             i = 5

0.1667

0.1667

0.0547

0.0547

.4478

Thus maximum is the probability of the robot being in the state of 5. which is true, as you might have observed, that the only possible way the robot could have most favorably measured Red and Blue consecutively after each motion if it would have been in Step 3 initially. Thus after 2 motions it will be in step 5.

Voila, you have aced the first step of Robotics, Localization concept must have got embedded in your mind. Best of luck for your future in Robotics.

A lot many blogs are to come, so do not forget to subscribe and like this blog.

Regards 

Harshal

P.S. Next to Come
1. Localization for Dilettante
2. Localization for Experts

keep a watch at this blog for the links to the new blogs.

Motor Types and the bingo choice - Obfuscating Hobbyists since Ages

Robots do numerous tasks. Centered to all these tasks is movement. Movement in robotic terms is also known as actuation. Actuation can be linear, where robot or its parts moves in straight line; or rotational, where it rotates about a fixed axis; or a mixture of rotation and translation where the robotic parts move around an axis which itself makes a translation or rotation about other axis.

By far the most popular actuators are electric motors that spin a wheel or gear, and linear actuators that control industrial robots in factories. But there are some recent advances in alternative types of actuators, powered by electricity, chemicals, or compressed air. Motors are of various types which can be categorized into three basic ones. 

1. continuous DC motor 
2. Stepper motor
3. Servo motor

I will be discussing each one of them in detail. The discussion will consist of their construction, working principle and the most important of all, the big question :

"Where to use what?"

Now that I have introduced the basic types let us dwell deep into each one of them.

Continuous DC Motor

Construction and Working Principle

Ironically the miniature motors has all the parts and construction of its big brother, employed in Electrical engineering as DC Machines.

It mainly consists of an armature core with armature winding laid down in the slots made in them. These wires end up in commutator slots. The commutator is brushed through copper brushes which carry the current. The external body is static and does not move mostly(until you use an Out-runner motor, which is a special version of DC motor, having no brushes, but an electronic commutator circuit for ensuring half cycle current reversal such that the motor can produce torque). It carries field coils in the protruding structures called pole shoe. They are, like armature coil supplied by external voltage.

The current flowing through field coil produces magnetic field, which interacts with the current in the armature coil to produce torque. The alternating nature of the current in the armature coil due to commutation by split rings ensures that torque is always in the positive direction in both half cycles.

T = K(I x B)      

T = Torque produced by the motors that is coupled with the shaft and eventually makes it move
I  = The current supplied to the armature coil = V/R
V = Voltage supplied to the motor.
R = Armature resistance of the motor  (Mentioned in the motor ratings)
B = The magnetic field produced bu current in the field coil
K = constant of proportionality

Enough of the bookish stuff. Now let us quickly jump down to real knowledge which every robotics hobbyist and specialists alike must have. I would like to pose these in a question answer format.

Q. How do you control the direction of the motor? (Level - Basic)
A. It is easy. Just reverse the connections of the two wires.

Q. What to do if one wants to run the motor at half its rated speed? (Level - Basic)
A. Reduce the voltage, such that it equals to half the rated voltage.

Q. What to do if one wants to run the motor at thrice its rated speed? (Level - Basic)
A. One might be tempted to increase the voltage to thrice the rated voltage. But that is certainly wrong. If done likewise, the motor will be overburdened, get heated up and consequently melt down. It is a good and safe practice to operate the motor no more than its rated voltage or at maximum for 1.5 times its rated voltage(that too for a very short time)

Q.How is voltage related to torque in a DC motor? (Level - Basic)
A. They are proportional to each other. Increasing the voltage increases the current (= V/R) and thus increases the torque (K. I x B).

Q. I see two current ratings in my motor - Operating current and Stall current. What are they? (Level - Medium)
A. Operating Current - This is the average amount of current the motor is expected to draw under a typical torque. Multiply this number by the rated voltage and you will get the average power draw required to run the motor. 

Stall Current -  This is when you power up the motor, but you put enough torque on it to force it to stop rotating. This is the maximum amount of current the motor will ever draw, and hence the maximum amount of power too. So you must design all control circuitry capable of handling this stall current. 

Q. What is motor heat sink? Is there a heat sink for motor as well? (Level - Medium)
A. It is something every electronic circuitry requires. It is not only used for regulators, as is a common misconception, but any device which gets heated up. If one wants to operate the motor above its rated voltage, one must certainly apply heat sink to the motor.

Q. What is Power Spikes? (Level - Hard)

A. There is a special case for DC motors that change directions. To reverse the direction of the motor, you must also reverse the voltage. However the motor has a built  in inductance and momentum which resists this voltage change. So for the short period of time it takes for the motor to reverse direction, there is a large power spike. The voltage will spike double the operating voltage. The current will go to around stall current. Thus one must design the power regulation circuitry of the motor to handle such extreme cases of heating due to power, current and voltage overload.

Q. What is Operating Torque and Stall Torque? (Level - Medium)

A. Operating Torque is the torque that the motor will produce at the rated conditions of the voltage supplied. The motor generally gives high efficiency for operation around operating condition. 

Stall Torque  is the torque required externally (like a hand - if you want to hurt yourself really bad) to stop the motor from rotating.

Added fact - When struggling with the choice of which motor to choose, always go with one having high torque rating and not high velocity rating.

Q. What are other ways to reduce the velocity of the motor? (Level - Hard)

A. I think the question should be , how to reduce the velocity, while ensuring at the same time that the efficiency of the motor is the maximum. There is a general rule for DC motors.

      "Motors run the most efficient when run at the highest possible speeds. "

One can't run the motor at full speed all the time. One trick to ensure higher efficiency as well as reduced speed is to use gears.

w = the velocity of each gear
D = Diameter of each gear
N = Number of teeth of each gear

But gearing automatically reduces efficiency. Each gear reduces the efficiency by 10%. So, say you have 3 gears in a gear train(you can't attain all the speeds with just one gear, as it will lead to huge diameter of gears and thus hurt miniature motors. Instead we use two to three gears in cascade to achieve the equivalent effect.). Then the total efficiency of the motor, now, is

Motor efficiency after three gears = (0.9)x(0.9)x(0.9)x Motor efficiency of original motor

Q. How to control the DC motors?

A. You need to know three aspects of controlling a DC motor:

     1. Encoders

     2. H- Bridge

     3. DC Motor braking mechanism

These three are topics by themselves. I will be providing detailed explanations to them in next set of blogs. So stay tuned.

Feel free to Google them for the time being. 

Stepper Motors

Construction and Working

A stepper motor is a type of DC motor which has a full rotation divided in an equal number of steps. It is a type of actuator highly compatible with numerical control means, as it is essentially an electro-mechanical converter of digital impulses into proportional movement of its shaft, providing precise speed, position and direction control in an open-loop fashion, without requiring encoders, end-of-line switches or other types of sensors as conventional electric motors require.

Working

DC brushed motors rotate continuously when voltage is applied to their terminals. The stepper motor is known by its important property to convert a train of input pulses (typically square wave pulses) into a precisely defined increment in the shaft position. Each pulse moves the shaft through a fixed angle. Stepper motors effectively have multiple "toothed" electromagnets arranged around a central gear-shaped piece of iron. The electromagnets are energized by an external control circuit, such as a micro-controller. To make the motor shaft turn, first, one electromagnet is given power, which magnetically attracts the gear's teeth. When the gear's teeth are aligned to the first electromagnet, they are slightly offset from the next electromagnet. This means that when the next electromagnet is turned on and the first is turned off, the gear rotates slightly to align with the next one. From there the process is repeated. Each of those rotations is called a "step", with an integer number of steps making a full rotation. In that way, the motor can be turned by a precise angle.

Now, since we have the basics of Stepper motor in our bag, lets quickly move through the question answer session. The session consists of the most common questions one asks for when trying to work with stepper motors.

Q. What are the three wires for in the stepper motor? What does each of the color of the wire mean? (Level - Medium)
A. This is one of the most common problems a hobbyist encounters. Let me explain you, that the colors of the wires have a meaning and follow a color code.
The number of wires in a stepper motors can be 4,6 or 8. The respective circuit diagram of a stepper motor is:

The color code can be found at this site: http://www.linengineering.com/resources/wiring_connections.aspx

Q. What is the relation between number of steps performed by stepper motor and number of control impulses? (Level - Basic)

A. When functioning correctly the number of steps performed must be equal to the control impulses applied to the phases of the motor.

Q. Does stepper motor employ closed loop or open loop control system? (Level - Basic)

A. To understand this question, one must know, first, that what is difference between open loop and closed loop control system.

Open-loop control system employs no feedback mechanism, that is at no stage, final or intermediate output is fed back as input to the system. Stepper motor is perfect example of open loop control system as its output only depends on the train of pulses which are provided as input, at no stage the output position, velocity or acceleration are fed into the system.

Closed-loop control systems are those systems that employ such feedback mechanism. For instance a DC motor using encoders for position or velocity feedback to control the position or velocity is an example of closed loop control system.

Q. Does a stepper motor fall back i.e lose steps i.e does not move for one or more pulses? (Level - Basic)

A.  A stepper motor does not lose steps, i.e. no slippage occurs, it remains synchronous to control impulses even from standstill or when braked, thanks to this characteristic a stepper motor can be started, stopped or reversed in a sudden fashion without losing steps throughout its operation.

Q. Where should one use stepper motors ans what are its limitations? (Level - Basic)

A.  The power range of a stepper motor varies from few micro-watts (uW) to no more than few kilowatts(kW). Thus they are used for low to medium power applications.

They are used mostly where high speed precision movements are required, than at places of heavy duty applications where torque is the point of concern.

Areas of applications - Plotters, Disc drivers, Robotic arm, Printers, CNC machines.

Q. You told us a lot of advantages. So is it all dream come true motor? (Level - Medium)

A. No! I think i got 80% optimistic and just 20% realistic

The stepper motor has its own set of disadvantages :-

     1.  Low torque capacity

     2.  Low power efficiency

     3.  Fixed step value for a given motor.

Q. What is unipolar and bipolar motors? What type is Stepper motors?

A. Unipolar motors : When the direction of the current supplied to the motor is not changed to change the direction of the motor. Then it is a Unipolar motor.

Bipolar motors: When the direction of the current must be changed to ensure a reversal in the direction of current, it is called bipolar motor. Eg. - Continuous DC motors

Stepper motors can be either of the two types depending on the types of stepper motor. Please follow the next question to find out the exact answer.

Q. What are the types of Stepper motors? (Level - Hard)

A. There are three types of stepper motors:

1. Variable Reluctance type - Reactive type
2. Permanent magnet type - Active type
3. Hybrid - Mixture of (1) and (2)

Variable Reluctance type

Courtesy: WikiForU.com

The rotor has teeth as shown in the figure. It is passive in nature as the control winding (the coils), are not on the rotor, but on the stator. By energizing one or more phases, the rotor will turn in such a manner that it settles on a minimum reluctance path.

There are two such paths:-

1. When the rotor teeth align with the stator teeth (also called stator pole).
2. When the rotor teeth align with the bisector of the stator pole.

Pros:

1. Helps in achieving small to medium step angles
2. Feasible to operate at high control frequencies.

Cons:

1. It can't hold its position i.e when no current flows through the stator winding, there is no stopping torque.

It is an example of Unipolar motor.The change in the direction of the motor is achieved through change in the impulse sequence.

Permanent Magnet Type

Courtesy: WikiForU.com

Stay tuned for the explanation. 

Hybrid Type 

Courtesy: WikiForU.com

Stay tuned for the explanation.


Q. Can you please help me with Stepper motor jargon? (Level - Medium)
A. Sure! why not. Here are few most important ones, one should be aware about.

1. Step Angle - It is the angle turned by the motor for one input impulse.
2. Pull-in torque - Represents the maximum torque load at the shaft, for which the motor can start without losing steps.
3. Pull-out torque - Maximum torque that the motor can maintain at a particular speed, without losing steps
4. Detent torque - It is the holding torque that the motor torque offers when it is not energized. 
5. Angular speed - Angular speed = (Stepping Angle) x (Control Frequency)
6. Maximum Frequency - It is the maximum frequency at which a motor can remain synchronized with the input train of pulses. 

Q. How to control a stepper motor? (Level - Hard)
A. This is a topic in itself. I will be posting the link to this question in a separate blog. So stay tuned for the link to that blog under this question at a later stage. But for tha sake of introduction,
There are actually 4 types of control system for the stepper motor:

1. Half step drive
2. Full step drive
3. Wave drive
4. Micro-stepping drive

Q. What is Ringing and Resonance in Stepper motor? (Level - Medium)

A. When the motor moves a single step it overshoots the final resting point and oscillates round this point as it comes to rest. This undesirable ringing is experienced as motor vibration and is more pronounced in unloaded motors. An unloaded or under loaded motor may, and often will, stall if the vibration experienced is enough to cause loss of synchronisation.

Stepper motors have a natural frequency of operation. When the excitation frequency matches this resonance the ringing is more pronounced, steps may be missed, and stalling is more likely. Motor resonance frequency can be calculated from the formula:

M_h   = Holding torque cN·m
p      = Number of pole pairs
J_r     = Rotor inertia kg·cm²

Servo Motor

Construction and Working Principle

This is nothing but a simple electric motor, controlled with the help of servomechanism. If the motor as controlled device, associated with servomechanism is DC servo, then it is commonly known DC Servo Motor. If the controlled motor is operated by AC, it is called AC Servo Motor.

The working principle is same as the DC motor (as visible in the break apart motor shown above), but with an added velocity or position feedback achieved using a potentiometer.

Control Mechanism

The entire control mechanism can be very easily understood using the figure cum circuit illustration shown below.

ServoMechanism

The position of the output, measured by the potentiometer, is continually compared to the commanded position from the control (i.e., the radio control). Any difference gives rise to an error signal in the appropriate direction, which drives the electric motor either forwards or backwards, and moving the output shaft to the commanded position. When the servo reaches this position, the error signal reduces and then becomes zero, at which point the servo stops moving.

If the servo position changes from that commanded, whether this is because the command changes, or because the servo is mechanically pushed from its set position, the error signal will re-appear and cause the motor to restore the servo output shaft to the position needed.

Now let us come down to few typical questions that comes in mind of a robotics aspirant.

Q. How many wires are used and is there a color code for the wires? (Level - Basic)
A. Yes, there are three wires in a servo motor.

•  Black or Brown - Ground
•  Red - Live
•  Yellow or White - Control Signal wire 

Q. What are the types of Servomotors? (Level - Basic)
A. There are basically three types of servomotors.

• Positional rotation servo: This is the most common type of servo motor. The output shaft rotates in about half of a circle, or 180 degrees. It has physical stops placed in the gear mechanism to prevent turning beyond these limits to protect the rotational sensor. These common servos are found in radio-controlled cars and water- and aircraft, toys, robots, and many other applications.
• Continuous rotation servo: This is quite similar to the common positional rotation servo motor, except it can turn in either direction indefinitely. The control signal, rather than setting the static position of the servo, is interpreted as the direction and speed of rotation. The range of possible commands causes the servo to rotate clockwise or counterclockwise as desired, at varying speed, depending on the command signal. You might use a servo of this type on a radar dish if you mounted one on a robot. Or you could use one as a drive motor on a mobile robot. In such servos the input pulse results in a rotational speed, and the typical 1.5 ms center value is the stop position. A smaller value should turn the servo clockwise and a higher one anticlockwise.
• Linear servo: This is also like the positional rotation servo motor described above, but with additional gears (usually a rack and pinion mechanism) to change the output from circular to back-and-forth. These servos are not easy to find, but you can sometimes find them at hobby stores where they are used as actuators in larger model airplanes.

Q. What is PWM and how is it used to run the servomotor? (Level - Hard)
A. PWM stands for Pulse Width Modulation. It is a control signal that is fed into the control wire of the servo motor. 
In general a PWM signal and its corresponding servo position looks like this:

Each servo's requirements vary slightly, but a pulse train (as in Figure above) of about 50 to 60 Hz works well for most models. The pulse width will vary from approximately 1 millisecond to 2 or 3 milliseconds (one millisecond is 1/1000 of a second). 

NOTE :

1. I will be updating this blog in near future to make it more complete. So kindly stay tuned with this page.
2. This is a very introductory blog for beginners to come at scale with the experts. The level of difficulty will keep on increasing
3. I will be posting blogs related to 

• Under-actuated Robotics
• Computer Vision
• Artificial Intelligence
• Machine Learning
• Mobile Robotics

I will try to post one blog a day, so you can expect a lot of in depth information related to robotics at a place. 

Do like and comment, Your suggestions for topics to cover are most welcomed.