Greetings
Until the NXT time it is! If you picked up from the last post, you would have guessed that the NeXT post is going to something about Mindstorms NXT. And it is. In this post I am briefly going to talk about a technology which has united my two greatest passions: Programming and Robotics! Mindstorms, by Lego, is a Robotics Kit which one use to build and program fully or partially autonomous programmable robots (Robots including, but not limited to bipedal humanoids). Lego Mindstorms was released following a collaboration between Lego and MIT's Media Lab. The Lego Mindstorms started out as Mindstorms v1.0 and the latest version now is the Mindstorms NXT v2.0, a huge leap from its predecessors in terms of processing power by the Mindstorms Brick and availability of different kinds of sensors. Lego Mindstorms NXT is programmable through the NXT-G programming software(simple programs can be built on the Brick itself), which supports Visual Programming. I, however owning to my hacker nature, decided to go one step forward and installed the LeJOS firmware on my NXT. LeJOS allows the NXT to execute special byte-code from LeJOS specific java programs! This means that you can code all you NXT programs in leJOS Java(similar to Java ME), convert it to special byte-code with the help of LeJOS NXJ on your computer(similar to the java JDK) and transfer the byte-code to the NXT and execute it using the LeJOS Virtual Machine. As one can see, the ability to use such a powerful language greatly increases the possibilities of the Mindstorms NXT. Also LeJOS can be used to communicate(2 way data streams) with other Java programs, whether they reside in a computer, a smart phone or even another NXT! Using you cellphone to control your NXT or developing a Client-Server relationship between the NXT and the computer can be achieved through LeJOS. The methods of communication are BlueTooth and the USB specifications. LeJOS is the not the only custom firmware for the NXT; ROBOTC and BrickOS can be used to run c/c++ programs on the NXT. For now however, I will be sticking to LeJOS. I will soon be posting a page on how exactly to get LeJOS on your NXT, as well as many clever, innovate programs for LeJOS NXT. Until then, take a look at a list of useful sites that I have posted down below!
Never The End.
******************
**Some Useful Sites**
******************
The LeJOS API
The LeJOS PC API
Great NXT tutorials
A NXT LeJOS forum
Monday, January 3, 2011
Thursday, November 25, 2010
Day of the Knight
Recursion n. See recursion
Search v. Definition hidden at the end
Greetings
I am came across an interesting problem sometime back on the net. The problem in a nutshell was to calculate the least of amount of steps that it would take a knight to get from square(a,b) to square(x,y). The real task at hand was to map out the whole chessboard, with values denoting the depth or breadth level from the starting square. This question could be solved two ways, using either the Depth First Search Method, or the Breadth First Search Method. I am going to speak about them in this post.
DEPTH FIRST SEARCH:
The Depth First Search or DFS is a recursive searching method, where by, on goes down as long as they can until they hit a dead end. When they do, they go one up, and starting going down again, although this time in a different path. Consider it like this. Imagine a house full of rooms. Inside these rooms there are more rooms, inside which there are even more. Your task is to find how many rooms one has to go through to get to room 8. Diagram given below.
In a typical DFS search, the longest search order would be something like this:
Start->1->4(Dead End!)->1->5->9->5->1->Start->2->6->10->6->11->6->2->Start->3->7->12->7->3->8
In a typical DFS search, the shortest search order would be something like this:
Start->3->8
...............and many possible permutations in between.
As you can see, something that is just two levels away from the start takes a maximum of 23 node visits, where as the shortest one takes just 3 node visits. There is no way to ensure the DFS method to make the shortest node visits, as the DFS wont know the location of the node in absolute terms, only in relationship to other nodes. In part, the DFS has such a high, unacceptable worst case scenario result is because many of the nodes are re-visited many times over.(Start, 1, 5, etc). The difference between the best and worst cases is way too big for the search to be efficient.
BREADTH FIRST SEARCH
The search technique in BFS involves grouping nodes with the same absolute distance nodal distance from Start Point in the same breadth. Imagine that after the BFS technique identifies the nodes with nodal distance 1 from the start point. All these nodes are in Breadth Level 1. These nodes will then be pushed into a stack, where EACH on of these nodes will become the Start Point. Now the nodes with a nodal distance of 1 from these Start points will be grouped in Breadth Level 1 more than than the breadth level of their starting points, something like (Node Level = Start Point Level + 1). In this manner all the nodes will be mapped and assigned a value denoting their absolute nodal distance from the first Start Point. Here is a diagram.
In a typical BFS search the search order would be something like this:
Start->1,2,3 stack.push(1,2,3)-1st Level
loop through stack as long as there are nodes.
1->4,5 stack.pop(1) stack.push(4,5)-2nd Level
2->6 stack.pop(2) stack.push(6)-2nd Level
3->7,8 stack.pop(3) stack.push(7,8)-2nd Level //Stop here, 8 is found
4->Dead End! stack.pop(4)-3rd Level
5->9 stack.pop(5) stack.push(9)-3rd Level
6->10,11 stack.pop(6) stack.push(10,11)-3rd Level
7->12 stack.pop(7) stack.push(12)-3rd Level
8->Dead End! stack.pop(8) -3rd Level
9->Dead End! stack.pop(9) -4th Level
10->Dead End! stack.pop(10) -4th Level
11->Dead End! stack.pop(11) -4th Level
12->Dead End! stack.pop(12) -4th Level
Another, faster case
Start->3,2,1 stack.push(3,2,1)-1st Level
loop through stack.
3->7,8 stack.pop(3) stack.push(7,8)-2nd Level //Stop here, 8 is found
As you can see, each node is not visited more than once, only its location is pushed into the stack. After its immediate nodes are visited, it should be popped out or removed, otherwise you will have an infinite loop.
The difference between the best and worst case scenarios is not much, and is generally more efficient than DFS, as it takes less time, resources and searched intuitively.
The C++ program that I built also uses the same technique of BFS to solve the problem. Have a look at it, annotations are included and post your feedback or questions regarding the program.
Link for the .cpp File
Link for the .exe File
Until the NXT post
Aravind Rao, chief Hacker(claimed)
Search v. Definition hidden at the end
Greetings
I am came across an interesting problem sometime back on the net. The problem in a nutshell was to calculate the least of amount of steps that it would take a knight to get from square(a,b) to square(x,y). The real task at hand was to map out the whole chessboard, with values denoting the depth or breadth level from the starting square. This question could be solved two ways, using either the Depth First Search Method, or the Breadth First Search Method. I am going to speak about them in this post.
DEPTH FIRST SEARCH:
The Depth First Search or DFS is a recursive searching method, where by, on goes down as long as they can until they hit a dead end. When they do, they go one up, and starting going down again, although this time in a different path. Consider it like this. Imagine a house full of rooms. Inside these rooms there are more rooms, inside which there are even more. Your task is to find how many rooms one has to go through to get to room 8. Diagram given below.
 |
| The room location map. |
In a typical DFS search, the longest search order would be something like this:
Start->1->4(Dead End!)->1->5->9->5->1->Start->2->6->10->6->11->6->2->Start->3->7->12->7->3->8
In a typical DFS search, the shortest search order would be something like this:
Start->3->8
...............and many possible permutations in between.
As you can see, something that is just two levels away from the start takes a maximum of 23 node visits, where as the shortest one takes just 3 node visits. There is no way to ensure the DFS method to make the shortest node visits, as the DFS wont know the location of the node in absolute terms, only in relationship to other nodes. In part, the DFS has such a high, unacceptable worst case scenario result is because many of the nodes are re-visited many times over.(Start, 1, 5, etc). The difference between the best and worst cases is way too big for the search to be efficient.
BREADTH FIRST SEARCH
The search technique in BFS involves grouping nodes with the same absolute distance nodal distance from Start Point in the same breadth. Imagine that after the BFS technique identifies the nodes with nodal distance 1 from the start point. All these nodes are in Breadth Level 1. These nodes will then be pushed into a stack, where EACH on of these nodes will become the Start Point. Now the nodes with a nodal distance of 1 from these Start points will be grouped in Breadth Level 1 more than than the breadth level of their starting points, something like (Node Level = Start Point Level + 1). In this manner all the nodes will be mapped and assigned a value denoting their absolute nodal distance from the first Start Point. Here is a diagram.
 | ||
| The room Location Map, now with Breadth levels. |
Start->1,2,3 stack.push(1,2,3)-1st Level
loop through stack as long as there are nodes.
1->4,5 stack.pop(1) stack.push(4,5)-2nd Level
2->6 stack.pop(2) stack.push(6)-2nd Level
3->7,8 stack.pop(3) stack.push(7,8)-2nd Level //Stop here, 8 is found
4->Dead End! stack.pop(4)-3rd Level
5->9 stack.pop(5) stack.push(9)-3rd Level
6->10,11 stack.pop(6) stack.push(10,11)-3rd Level
7->12 stack.pop(7) stack.push(12)-3rd Level
8->Dead End! stack.pop(8) -3rd Level
9->Dead End! stack.pop(9) -4th Level
10->Dead End! stack.pop(10) -4th Level
11->Dead End! stack.pop(11) -4th Level
12->Dead End! stack.pop(12) -4th Level
Another, faster case
Start->3,2,1 stack.push(3,2,1)-1st Level
loop through stack.
3->7,8 stack.pop(3) stack.push(7,8)-2nd Level //Stop here, 8 is found
As you can see, each node is not visited more than once, only its location is pushed into the stack. After its immediate nodes are visited, it should be popped out or removed, otherwise you will have an infinite loop.
The difference between the best and worst case scenarios is not much, and is generally more efficient than DFS, as it takes less time, resources and searched intuitively.
The C++ program that I built also uses the same technique of BFS to solve the problem. Have a look at it, annotations are included and post your feedback or questions regarding the program.
Link for the .cpp File
Link for the .exe File
Until the NXT post
Aravind Rao, chief Hacker(claimed)
Friday, November 12, 2010
My First Program
Greetings
I have finally gotten around to uploading my first ever program to the web. It is a C++ program designed to find the number of primes in a range of numbers. Both the .cpp file and .exe file are uploaded, so please feel free to download, run, edit and redistribute them, with credit given! There are also explanations as to why and how the program works in the .cpp file.
Enjoy and Happy Coding!
Wednesday, November 10, 2010
Hello, World!
Greetings
And here is the first post. *Drum roll*. This blog has finally taken off after...............3 weeks. I have finally found some time to post some material to this blog, thanks to the long weekend. Anyway now that things have been set in motion(perpetual, I hope), I will soon be posting links to my own programs and source code, and describe how they work, and why they work. You can download them, edit them, redistribute them(feedback them?).......the possibilities are endless. Most of my programs will be in c++ or Java, and for those out there with Lego Mindstorms NXT, I will be posting programs for the LeJOS OS on the NXT. I also always have a ton of doubts and if you are a person who is more knowledgeable than me in the field of programming(you only have to be ahead by a class), please help me out!
This is not the end...........
Aravind Rao
Subscribe to:
Posts (Atom)