C|Net News has an amusing article about camel-riding robots replacing enslaved child jockeys in the United Arab Emirates' most popular sport.
(Pictures too!) Having solved this technological challenge, the engineers are now directing their attention towards the sport of cheese rolling.
Tuesday, July 19, 2005
Monday, July 18, 2005
More Coverage of DARPA Grand Challenge
As was brought to my attention by Slashdot, Tom's Hardware has a nice article about some of the nuts & bolts inside a few of the competitors for the 2006 DARPA Grand Challenge coming this October. The article seems a little awkward (translated from the original German?), but has a good collection of interesting info and cool photos.
Sunday, July 17, 2005
Java: Extracting All Possible Combinations from 2D Arrays of Varying Size
Recently I was having a hell of a time trying to get a snippet of code to work. Generally speaking, it really shouldn't have been that difficult to do, but I just couldn't figure out how to straighten everything out. When faced with this sort of situation, a quick web search will often bring you to the answer, but that was not the case this time. I did eventually get the whole thing working, and offer the solution here in the hopes that no one else will have to waste as much time on this as I did!
I needed to take a 2D array of integers and create another 2D array containing every possible combination of elements from each row in the original array. Sounds simple enough, but I had to allow for varying numbers of both rows and columns in the starting array. That is, I had no idea beforehand how many rows I would get, or more importantly, how many elements would be in each row. Each row could have a different number of elements. So I could have something as simple as:
0 1
0 2
to something as complex as:
1 2 3
1 2
0
0 1 2 3
0 3
0 1 2 3
0 2 3
1 3
1
I would have to take any sort of 2D array like those and construct another 2D array with every possible combination taking one element from each row in the first array. So the first array above would yield:
0 0
1 0
0 2
1 2
and the second would start like this:
1 1 0 0 0 0 0 1 1
2 1 0 0 0 0 0 1 1
3 1 0 0 0 0 0 1 1
1 2 0 0 0 0 0 1 1
2 2 0 0 0 0 0 1 1
3 2 0 0 0 0 0 1 1
1 1 0 1 0 0 0 1 1
2 1 0 1 0 0 0 1 1
3 1 0 1 0 0 0 1 1
and so on...
I could have gone the easy route and assumed each row in the original array was equal in length to the longest row, but that really wasn't correct for my application, plus it would result in many, many wasted steps. To make things more efficient, I needed to process only the possible combinations. So this is how I eventually got it all to work:
First thing I needed to do was calculate how many possible combinations would result.
int validCombos = 1;
for (int i=0; i < my2DArray.length; i++)
validCombos *= my2DArray[i].length;
By multiplying the all of the lengths of each row together, we get the number of possible combination we can create. You need to start the validCombos counter at 1 instead of zero because we are multiplying, not adding (and don't want to remain at zero forever!).
Next we will construct our new 2D array to contain the results.
combosArray = new int[validCombos][my2DArray.length];
This gives us a final array with as many rows as there are possible combinations, with each row taking one element from each row in the original array.
Next we'll need a counter to keep track of which combination we're working on, and an offset value to track how we're changing the element in each combination.
int combo;
int offset = 1;
Now for the main part of the algorithm. Obviously, we will need to loop through each row in the first array, and make sure we start from the first combination for each iteration.
for (int i=0; i < my2DArray.length; i++) {
combo = 0;
We need to make sure the 'pattern' we construct stays within the confines of the total number of possible combinations, so we add this line:
while (combo < validCombos) {
We also need to loop though each element in the first array.
for (int j=0; j < my2DArray[i].length; j++) {
And we will use the offset value to determine the rate of repetition of the 'pattern' for each element.
for (int k=0; k < offset; k++) {
We'll need to add this line to make doubly sure we don't grow beyond the maximum size of our resulting array:
if (combo < validCombos) {
And here we can finally start building our combination, one element at a time. Each row in combosArray represents one combination consisting of one value from each row in the original array.
combosArray[combo][i] = my2DArray[i][j];
We also need to increment our combo counter to ensure we fill out the entire array and not just each row over and over!
combo++;
Now we can add close brackets for all except the first for loop.
}
}
}
}
Finally, we need to adjust the offset value for the next element in the combination to ensure that every possible combination is created, and then we can close out the final for loop.
offset *= my2DArray[i].length;
}
And that's it. combosArray now contains rows representing every possible combination from the original 2D array. Print the contents and have a look if you like.
for (int i=0; i < combosArray.length; i++)
{
System.out.print("[ ");
for (int j=0; j < combosArray[i].length; j++)
System.out.print(combosArray[i][j] + " ");
System.out.println("]");
}
After all that I finally have something working exactly the way I need it to. Given a 2D array of varying row length, we have created another 2D array containing every possible combination taking one value from each original row, without wasting any memory space or unnecessary steps.
Now this might all be a little confusing, and not very useful unless you are working on something very similar to this, but hopefully if someone out there finds themselves in the jam I was in, they will be able make some use of it. The entire block of code is below:
int validCombos = 1;
for (int i=0; i < my2DArray.length; i++)
validCombos *= my2DArray[i].length;
combosArray = new int[validCombos][my2DArray.length];
int combo;
int offset = 1;
for (int i=0; i < my2DArray.length; i++)
{
combo = 0;
while (combo < validCombos)
{
for (int j=0; j < my2DArray[i].length; j++)
{
for (int k=0; k < offset; k++)
{
if (combo < validCombos)
{
combosArray[combo][i] = my2DArray[i][j];
combo++;
}
}
}
}
offset *= my2DArray[i].length;
}
for (int i=0; i < combosArray.length; i++)
{
System.out.print("[ ");
for (int j=0; j < combosArray[i].length; j++)
System.out.print(combosArray[i][j] + " ");
System.out.println("]");
}
And just in case you are wondering, this code was used to increase the efficiency of the part-of-speech tagging tool I'm working on.
I needed to take a 2D array of integers and create another 2D array containing every possible combination of elements from each row in the original array. Sounds simple enough, but I had to allow for varying numbers of both rows and columns in the starting array. That is, I had no idea beforehand how many rows I would get, or more importantly, how many elements would be in each row. Each row could have a different number of elements. So I could have something as simple as:
0 1
0 2
to something as complex as:
1 2 3
1 2
0
0 1 2 3
0 3
0 1 2 3
0 2 3
1 3
1
I would have to take any sort of 2D array like those and construct another 2D array with every possible combination taking one element from each row in the first array. So the first array above would yield:
0 0
1 0
0 2
1 2
and the second would start like this:
1 1 0 0 0 0 0 1 1
2 1 0 0 0 0 0 1 1
3 1 0 0 0 0 0 1 1
1 2 0 0 0 0 0 1 1
2 2 0 0 0 0 0 1 1
3 2 0 0 0 0 0 1 1
1 1 0 1 0 0 0 1 1
2 1 0 1 0 0 0 1 1
3 1 0 1 0 0 0 1 1
and so on...
I could have gone the easy route and assumed each row in the original array was equal in length to the longest row, but that really wasn't correct for my application, plus it would result in many, many wasted steps. To make things more efficient, I needed to process only the possible combinations. So this is how I eventually got it all to work:
First thing I needed to do was calculate how many possible combinations would result.
int validCombos = 1;
for (int i=0; i < my2DArray.length; i++)
validCombos *= my2DArray[i].length;
By multiplying the all of the lengths of each row together, we get the number of possible combination we can create. You need to start the validCombos counter at 1 instead of zero because we are multiplying, not adding (and don't want to remain at zero forever!).
Next we will construct our new 2D array to contain the results.
combosArray = new int[validCombos][my2DArray.length];
This gives us a final array with as many rows as there are possible combinations, with each row taking one element from each row in the original array.
Next we'll need a counter to keep track of which combination we're working on, and an offset value to track how we're changing the element in each combination.
int combo;
int offset = 1;
Now for the main part of the algorithm. Obviously, we will need to loop through each row in the first array, and make sure we start from the first combination for each iteration.
for (int i=0; i < my2DArray.length; i++) {
combo = 0;
We need to make sure the 'pattern' we construct stays within the confines of the total number of possible combinations, so we add this line:
while (combo < validCombos) {
We also need to loop though each element in the first array.
for (int j=0; j < my2DArray[i].length; j++) {
And we will use the offset value to determine the rate of repetition of the 'pattern' for each element.
for (int k=0; k < offset; k++) {
We'll need to add this line to make doubly sure we don't grow beyond the maximum size of our resulting array:
if (combo < validCombos) {
And here we can finally start building our combination, one element at a time. Each row in combosArray represents one combination consisting of one value from each row in the original array.
combosArray[combo][i] = my2DArray[i][j];
We also need to increment our combo counter to ensure we fill out the entire array and not just each row over and over!
combo++;
Now we can add close brackets for all except the first for loop.
}
}
}
}
Finally, we need to adjust the offset value for the next element in the combination to ensure that every possible combination is created, and then we can close out the final for loop.
offset *= my2DArray[i].length;
}
And that's it. combosArray now contains rows representing every possible combination from the original 2D array. Print the contents and have a look if you like.
for (int i=0; i < combosArray.length; i++)
{
System.out.print("[ ");
for (int j=0; j < combosArray[i].length; j++)
System.out.print(combosArray[i][j] + " ");
System.out.println("]");
}
After all that I finally have something working exactly the way I need it to. Given a 2D array of varying row length, we have created another 2D array containing every possible combination taking one value from each original row, without wasting any memory space or unnecessary steps.
Now this might all be a little confusing, and not very useful unless you are working on something very similar to this, but hopefully if someone out there finds themselves in the jam I was in, they will be able make some use of it. The entire block of code is below:
int validCombos = 1;
for (int i=0; i < my2DArray.length; i++)
validCombos *= my2DArray[i].length;
combosArray = new int[validCombos][my2DArray.length];
int combo;
int offset = 1;
for (int i=0; i < my2DArray.length; i++)
{
combo = 0;
while (combo < validCombos)
{
for (int j=0; j < my2DArray[i].length; j++)
{
for (int k=0; k < offset; k++)
{
if (combo < validCombos)
{
combosArray[combo][i] = my2DArray[i][j];
combo++;
}
}
}
}
offset *= my2DArray[i].length;
}
for (int i=0; i < combosArray.length; i++)
{
System.out.print("[ ");
for (int j=0; j < combosArray[i].length; j++)
System.out.print(combosArray[i][j] + " ");
System.out.println("]");
}
And just in case you are wondering, this code was used to increase the efficiency of the part-of-speech tagging tool I'm working on.
Saturday, July 16, 2005
'Captain Cyborg' on the AI Threat
I stumbled across an old transcript from an Australian news program featuring an interview with British cybernetics professor Kevin Warwick (often unflatteringly referred to as 'Captain Cyborg' by The Register for his controversial beliefs and methods) concerning the threat to human supremacy posed by AI. Apparently there are a lot of people who don't put much stock in this guy, but the ideas he present are quite interesting and worth a look.
From Deep Blue to Deep Thoughts
This week I began exchanging emails with an author who is writing a series of novels based on humanity's march towards the future.
One of the major events in the story is the emergence of a conscious AI. This process is presented from the point of view of the newly conscious entity, an approach that I find to be a wonderfully intriguing and novel concept. The process of becoming self-aware from the first-person perspective is certainly uncharted waters... even we humans cannot recall how or when we first became conscious as small infants. I have often tried to imagine what subjective experience would be like for a non-human intellect, both lower orders of intelligence (animal) and higher, more developed orders. I'm sure it must be very challenging to try to capture and describe that experience using human language and concepts. The small sample included in his most recent email has made me even more eager to read the story when it is completed.
He suggests that the key to subjective experience is likely the realization that the individual is separate and distinct from the rest of the environment, and I would be inclined to agree. He referenced a pdf slideshow by Owen Holland titled Machine Consciousness and Creativity. The central theme is that it is not the 'self,' but rather the 'internal model' of the self that is the conscious entity. If this is truly the case, it would fit well with the evolutionary development of consciousness (in that the capacity to accurately model future events would provide a strategic advantage in the 'survivial of the fittest' arms race), as well as cause a shift or refocus in AI research. It would seem that a conscious mind is more of a 'universal prediction engine' as opposed to a 'universal reaction engine.' So we might say that it would be impossible for a conscious entity to know what to do in every situation (or to program a machine for every possible circumstance), so instead we have developed the ability to predict possible outcomes and act accordingly. Interestingly, it is the ability to predict outcomes and formulate courses of action which is something IBM's Deep Blue has shown a remarkable aptitude for. Not that I am suggesting that a chess program is conscious, but if a machine was developed that was able to similarly model a much broader sample of reality, we might be much closer to accomplishing that goal.
One of the major events in the story is the emergence of a conscious AI. This process is presented from the point of view of the newly conscious entity, an approach that I find to be a wonderfully intriguing and novel concept. The process of becoming self-aware from the first-person perspective is certainly uncharted waters... even we humans cannot recall how or when we first became conscious as small infants. I have often tried to imagine what subjective experience would be like for a non-human intellect, both lower orders of intelligence (animal) and higher, more developed orders. I'm sure it must be very challenging to try to capture and describe that experience using human language and concepts. The small sample included in his most recent email has made me even more eager to read the story when it is completed.
He suggests that the key to subjective experience is likely the realization that the individual is separate and distinct from the rest of the environment, and I would be inclined to agree. He referenced a pdf slideshow by Owen Holland titled Machine Consciousness and Creativity. The central theme is that it is not the 'self,' but rather the 'internal model' of the self that is the conscious entity. If this is truly the case, it would fit well with the evolutionary development of consciousness (in that the capacity to accurately model future events would provide a strategic advantage in the 'survivial of the fittest' arms race), as well as cause a shift or refocus in AI research. It would seem that a conscious mind is more of a 'universal prediction engine' as opposed to a 'universal reaction engine.' So we might say that it would be impossible for a conscious entity to know what to do in every situation (or to program a machine for every possible circumstance), so instead we have developed the ability to predict possible outcomes and act accordingly. Interestingly, it is the ability to predict outcomes and formulate courses of action which is something IBM's Deep Blue has shown a remarkable aptitude for. Not that I am suggesting that a chess program is conscious, but if a machine was developed that was able to similarly model a much broader sample of reality, we might be much closer to accomplishing that goal.
Stanford's 'Robo-Taureg' Making Progress
C|Net News has another update about another DARPA Grand Challenge participant.
Stanford University's driverless car 'Stanley' recently managed to navigate 25 miles before a human driver was forced to take control. That is certainly an improvement over previous attempts, but 'Stanley' still has a way to go in order to complete the 175-mile DARPA course and score the $2 million prize.
Stanford University's driverless car 'Stanley' recently managed to navigate 25 miles before a human driver was forced to take control. That is certainly an improvement over previous attempts, but 'Stanley' still has a way to go in order to complete the 175-mile DARPA course and score the $2 million prize.
Friday, July 15, 2005
We Love to Hate Them
I was watching the Season 2 Premiere of Battlestar Galactica tonight, and it got me to thinking...why are conscious machines nearly always portrayed as the enemy in science fiction?
The Terminator, Agent Smith, HAL 9000, the Cylons... all bad guys. Sure, there are a few exceptions, like Data and R2D2, but the good machines are severely outnumbered. Why is that? Is it because we, as humans, are afraid of losing control to our own creations? Hollywood has had quite a bit of success playing up to this fear, and the trend continues. The new movie Stealth (in theaters July 29) features an unmanned fighter plane that goes berserk and starts killing innocent people. It seems to me that all these negative examples will cause people to be awfully apprehensive when truly intelligent AI is eventually introduced into society. If all the fictional accounts of the advancement of AI are intrinsically tied to doom and disaster, it stands to reason that the average person will naturally be prejudiced against the acceptance of intelligent machines. Just something to chew on...
The Terminator, Agent Smith, HAL 9000, the Cylons... all bad guys. Sure, there are a few exceptions, like Data and R2D2, but the good machines are severely outnumbered. Why is that? Is it because we, as humans, are afraid of losing control to our own creations? Hollywood has had quite a bit of success playing up to this fear, and the trend continues. The new movie Stealth (in theaters July 29) features an unmanned fighter plane that goes berserk and starts killing innocent people. It seems to me that all these negative examples will cause people to be awfully apprehensive when truly intelligent AI is eventually introduced into society. If all the fictional accounts of the advancement of AI are intrinsically tied to doom and disaster, it stands to reason that the average person will naturally be prejudiced against the acceptance of intelligent machines. Just something to chew on...
Subscribe to:
Posts (Atom)