Sunday, May 31, 2015

Implementing Object Detection Based on Color in Webot Simulator for E-puck

This project was implemented by Richa AGARWAL, Taner GUNGOR and Pramita WINATA.

Abstract-Object detection and recognition is a challenging task in computer vision systems. So it was decided to work with E-puck for the same. But using a real e-puck connected with the system through bluetooth it is diffucult to transfer images captured by the robot's camera. So, it was decided to use Webot simulator for E-puck robot to develope and test the algorithm to detect objects using the color of an object. Where robot scans for the object if detects the goal, it moves in the direction of goal avoiding obstacles, else moves randomly in the arena looking for the goal (red object). The most relevant aspects of the simulator and implementation are explained.
Keywords-Webot simulator, e-puck, path planning


INTRODUCTION
We are implementing a simple object detection algorithm in Webot simulator for E-puck using C controller. The algorithm is designed to detect red objects using E-puck's camera. It is easier to control and grab images from E-puck robot using Webot simulator and controler.

1 - WEBOTS SIMULATOR
Webots is a development environment used to model, program and simulate mobile robots. With Webots the user can design complex robotic setups, with one or several, similar or different robots, in a shared environment. The properties of each object, such as shape, color, texture, mass, friction, etc., are chosen by the user. A large choice of simulated sensors and actuators is available to equip each robot. The robot controllers can be programmed with the built-in IDE or with third party development environments. The robot behavior can be tested in physically realistic worlds. The controller programs can optionally be transferred to commercially available real robots. Webots is used by over many universities and research centers worldwide. The development time you save is enormous.

Figure-1: Webots development stages

Webots allows you to perform 4 basic stages in the development of a robotic project Model, Program, Simulate and transfer as depicted on the Fig. 1.

Tuesday, May 26, 2015

Understanding k-Nearest Neighbour

Goal

In this chapter, we will understand the concepts of k-Nearest Neighbour (kNN) algorithm.

Theory

kNN is one of the simplest of classification algorithms available for supervised learning. The idea is to search for closest match of the test data in feature space. We will look into it with below image.



In the image, there are two families, Blue Squares and Red Triangles. We call each family as Class. Their houses are shown in their town map which we call feature space. (You can consider a feature space as a space where all datas are projected. For example, consider a 2D coordinate space. Each data has two features, x and y coordinates. You can represent this data in your 2D coordinate space, right? Now imagine if there are three features, you need 3D space. Now consider N features, where you need N-dimensional space, right? This N-dimensional space is its feature space. In our image, you can consider it as a 2D case with two features).

Now a new member comes into the town and creates a new home, which is shown as green circle. He should be added to one of these Blue/Red families. We call that process, Classification. What we do? Since we are dealing with kNN, let us apply this algorithm.

Tuesday, May 12, 2015

Robot Navigation - Rapidly-Exploring Random Tree Algorithm

Objective

The aim of this post is to understand the rapidly-exploring random tree and implement it in Matlab.

1 - Introduction

A rapidly exploring random tree (RRT) is an algorithm designed to efficiently search nonconvex, high-dimensional spaces by randomly building a space-filling tree. The tree is constructed incrementally from samples drawn randomly from the search space and is inherently biased to grow towards large unsearched areas of the problem. It widely used in autonomous robotic path planning.

2 - The Algorithm

RRTs were proposed as both a sampling algorithm and a data structure designed to allow fast searches in high-dimensional spaces in motion planning. RRTs are progressively built towards unexplored regions of the space from an initial configuration as shown in Figure 1.


Progressive construction of an RRT.

At every step a random $q\_rand$ configuration is chosen and for that configuration the nearest configuration already belonging to the tree $q\_near$ is found. For this a definition of distance is required (in motion planning, the euclidean distance is usually chosen as the distance measure). When the nearest configuration is found, a local planner tries to join $q\_near$ with qrand with a limit distance . If $q\_rand$ was reached, it is added to the tree and connected with an edge to $q\_near$. If $q\_rand$ was not reached, then the configuration $q\_new$ obtained at the end of the local search is added to the tree in the same way as long as there was no collision with an obstacle during the search. This operation is called the Extend step, illustrated in Figure 2. This process is repeated until some criteria is met, like a limit on the size of the tree.

Friday, May 1, 2015

Robot Navigation - A Star Algorithm

Objective

The aim of this lab is to understand the A* algorithm and implement it in Matlab.

1 - Introduction

In computer science, A* is a computer algorithm that is widely used in pathfinding and graph traversal, the process of plotting an efficiently traversable path between points, called nodes. A* achieves better time performance by using heuristics.

2 - The Algorithm

A* uses a best-first search and finds a least-cost path from a given initial node to the goal node. As A* traverses the graph, it follows a path of the lowest expected total cost or distance, keeping a sorted priority queue of alternate path segments along the way.

It uses a knowledge-plus-heuristic cost function of node x to determine the order in which the search visits nodes in the tree. The cost function is a sum of two functions:
  1. the past path-cost function, which is the known distance from the starting node to the current node x (denoted g(x))
  2. a future path-cost function, which is an admissible "heuristic estimate" of the distance from x to the goal (denoted h(x)).
The h(x) part of the f(x) function must be an admissible heuristic; that is, it must not overestimate the distance to the goal. Thus, for an application like routing, h(x) might represent the straight-line distance to the goal, since that is physically the smallest possible distance between any two points or nodes.

If the heuristic h satisfies the additional condition h(x) = d(x,y) + h(y) for every edge (x, y) of the graph (where d denotes the length of that edge), then h is called consistent. In such a case, A* can be implemented more efficiently. No node needs to be processed more than once and. Now let's look at closely to the each steps.