Wednesday 22 March 2017

Dijkstra Algorithm

Hello readers!
When one wants to reach a place (destination) from it's starting point, it's quite obvious that he/she would like to trace a shorter path, and not a longer one eluding the neighboring obstacles. So, here we are discussing an algorithm which finds the shortest path between the starting point and the destination node in a given graph.

Typically, F=lia, where, lia is the shortest distance from the node i to the node a in the given network, and F is the sum between the distance start node and end node, and estimate as to how much distance is left to reach the goal location.

So, in this algorithm the nodes visits all the adjacent nodes, that it, it expands in all directions and the distance which is traversed from the initial node to the next node is compared with the previous parent node, and then the shortest distance is decided, this is the biggest disadvantage of Dijkstra Algorithm, that it does blind search, as it has to check all the nodes and compare the newly calculated tentative distance value to the current assigned value, and chose the smallest value. That is why it grows comparatively slow than to Astar algorithm. And other disadvantage is that, it can't work for negative edges.

As, it can be seen from the video that the colour map is as follows:
  1. White - clear cell
  2.  Black - obstacle
  3. Red = visited
  4. Blue  - on list
  5. Green - startY
  6. Yellow - destination


This was a course on CourseraComputational Planning, the coding had to be done by oneself. We have done the coding on MATLAB.

Video of path planning algorithm: https://youtu.be/_V6-HSh5vDc


Sunday 19 March 2017

GAP,GATT & Beacon

In the previous article Exploring BLE through nRF51 DK development board, we mentioned briefly about BLE and nRF51-dk. In this article we will be explaining two important concepts which are required to code a bluetooth application.

Before that you should know that bluetooth network model is based on 'proximity networking'  which implies that when two devices come into range of each other, they are capable of establishing a connection.
The advertising takes place in following ways:
1. GAP:

GAP is an acronym of Generic Access Profile, it is used to control the advertising and defines various roles of the devices.It is responsible for your device to be visible to the outer world.

Devices can be divided in the following two roles:
1. Peripheral : These devices are small and are restricted to lesser resources. They are used to connect to much more powerful central devices. eg: heart rate monitoring watches, beacons.
2. Central: These devices are with greater processing power and memory. eg: phones, tablets etc.

There are two ways to send advertising out with GAP. The Advertising Data payload and the Scan Response payload.

Peripheral Devices sets an advertising interval , and sends the advertising data in that duration. The Advertising Data is essential for peripheral device , as it signifies its existence to any nearby listening devices.
Scan Response is sent out by central device , if required for additional information from the peripheral.

During advertising process, a single peripheral advertising data can be scanned by two or more central devices as shown in the figure below.This is known as broadcasting.

                                                              Figure 1 Broadcast Topology

In our project we are using beacons. Please visit the first link to know what are beacons and how do they work.
Beacons advertise themselves by sending  advertising data, which can be of 47 bytes in length and consist of :
1 byte preamble
4 byte access address
2-39 bytes advertising channel PDU
3 bytes CRC

                                                                    Figure 2 Advertised Data

As shown in the figure above PDU contains header, MAC and Data upto 31 bytes.
The Data of 31 bytes contains Beacon prefix, Proximity UUID , Major , Minor and TX power as shown in the figure.
                                                               Figure 3 Inside the Data Bytes

Our task was to scan the beacons using nRF51-dk. We used the example code BLE_Observer , which scans the beacons and returns the values of MAC address, RSSI, Scan response , Advertising type,Proximity UUID , Major , Minor and TX power .

The main purpose of peripheral to advertise is to establish a connection with the central device.
Once the connection occurs advertising process ends and we use GATT services and characteristics to communicate in both directions.

BLE devices can operate in a non-connectable advertisement-only mode (where all the information is contained in the advertisement), but they can also allow connections (and usually do).
In our project , we are using only GAP and we have used it in our scanner.

2. GATT:

GATT is an acronym for the Generic Attribute Profile, and it defines the way that two Bluetooth Low Energy devices transfer data back and forth using concepts called Services and Characteristics.
As mentioned above, GATT comes into play once a connection is established.
Now comes the interesting part, as said peripheral device can be scanned by two or more central devices. But once a connection is established , peripheral cannot advertise anymore and communicates with a single central device.
But a central device is capable of establishing connection with two or more peripheral devices. This kind of topology is called Connected Network Topology.
Figure 4 Connected Topology
An important concept which comes into play in GATT is server/client relationship.
We would recommend you to visit the second link  mentioned below to understand the concept.

Useful/ Recommended Links:
http://www.pointrlabs.com/blog/beacons-everything-you-need-to-know/
https://learn.adafruit.com/introduction-to-bluetooth-low-energy/gatt
 

Low cost Window Cleaning Robot: Challenges and much more!

So, after having a look at last post Sneak Peak, you might want to know quite a lot of things. And here, we will discuss everything but step wise.

Why window cleaning?

The  exteriors of many buildings are being constructed with Huge glass Panes  which give an immense aesthetic beauty, but cleaning the outer part of the building is a tough job. Generally, human labor clean the outer pane by clinging themselves to the high storied building which involves high life risk factor.
So, the motive of building this project was quite simple, it ensures safety of human labor, and also cuts the maintenance budget of commercial buildings. But since, we are still working on the model, it can be used for our home glass window panes.
Figure 1: Human labor cleaning exterior panes which has high risk factor


Attempt in making the robot:

The main challenge is to manage the weight of the body, our original idea was to fabricate the wheels of the robot in such a way that it could stick to the window. The wheel used was a pulley wheel with 4 cm width and 6 cm diameter, where we used flat suction cups of 2 cm diameter, which were fitted on the wheel, by drilling holes on the wheel. In this way, we had got around twenty four to thirty suction cups on a single wheel. So, the wheel with so many suction cups does stick on the window, but with the weight of the robot? Does it? Even if it takes the weight, will it stick along with vertical motion of robot?
This was a challenging task!
Before moving on, I would discuss the components that we have used to make the robot:
  1.  LiPo 11.1 Volts Battery: For powering up the controller as well as for driving the motors.
  2. DC Motor (10 RPM high torque 10 kg-cm)
  3. Arduino Mega: Control action
  4. Dual DC motor driver 20 Amperes
  5. Miscellaneous: Cleaning material.

Weight of the entire robot:

Components of robot
Weight (grams)
Wheels (Four)
152 gms
Acrylic Chassis
250 gms
DC Motor (Two)
360 gms
LiPo Battery 11.1V
140 gms
Arduino Mega
40 gms
Cleaning Purpose
40 gms
Total
980 gms


Now, we made a four wheel robot with all wheels fabricated with suction cups. The body is shown in figure. As per our calculations, the suction wheels took the weight of the robot perfectly. The robot got stuck to the window with all the components.

Designing our body:



Figure 2: Acrylic cutting

Figure 3: Mounting wheels in between


Figure 4: Mounting DC Motor


Figure 5: Final Acrylic chassis

So, keeping our fingers crossed we tried moving the robot, kick starting the motors the wheels didn't stick to the window and our robot fell down, which was heart breaking. This was the first failure and challenge we faced! So, our idea with having suction wheels went in vain, because by the time the other suction cup would come in contact with the window it slipped from the window.

Umm.. So what, we didn't give up that easily! We came up with other idea of creating suction the other way. The sneak peak post had the laser cutting fabrication of our new body, which would be discussed in the next post.




Figure 6: Robot stuck on window without motion


So readers, along with the weight, motion of the robot is also a challenging task of the previous model. But in the new model, we are not fabricating the wheels, we are changing the entire body, and made it quite compact, where we narrowed down the size and weight of the robot.