Monday, August 29, 2005

U.S. Army to Deploy Combat Robots in Iraq

The L.A. Times is reporting that the Army will deploy unmanned robotic ground vehicles into combat in Iraq later this year.

The robots, known as 'Tactical Amphibious Ground Support' and built by Northrop Grumman, will be the first autonomous ground vehicles used in a combat zone. The Army intends to use them for surveillance and border security missions, and the machines can navigate entirely on their own (although a remote operator can take control in the event of an emergency). Robots like the bomb-dismantling PackBot by iRobot have been serving in Iraq for quite some time, but this will mark the first use of completely autonomous vehicles in ground combat.

AI: Now and In the Future

Red Herring has a couple of excellent articles online regarding the present state and future possibilities of Artificial Intelligence.

The first article covers existing AI systems such as data mining and intelligence search, while the second chronicles Palm Pilot inventor Jeff Hawkins' quest to revolutionize the way we look at intelligence.

PHP: Longest Common Substring

While working on my answer machine program, I came across a need to find recurring patterns in strings. What I wanted to do was take two strings and return the longest substring contained by both. After about 30 minutes worth of searching Google for a quick solution, I realized that this was not a trivial problem. It seems that finding the longest common substring is a classical problem in computer science. Helpful examples of LCS algorithms were very hard to come by, and there was virtually nothing available for PHP. Maybe when I earn a PhD I will try to impress people with useless formulas and diagrams, but for now I figured I would just write some realtively straightforward code that gets the job done.

The solution that seemed the simplest to me was to compare the strings character by character looking for matches that would signify the possible beginning of a common substring. I really don't consider one character substrings to be significant, so my solution only initiates a match when it finds two identical substrings two characters in length. It continues down each string char-by-char as long they match, and then tosses the completed substring into an array. Every common substring is obtained this way, and then we simply return the longest of these as the result. If more than one common substring is longest, the one that appears first in the first source string is returned.

See it in action and view the source.

After all that, I'm starting to think it might be more appropriate for my application to tokenize the strings and then capture the longest common sequence of tokens. In other words, break the string down into words and return the longest common phrase. It won't be that much more difficult to implement both methods in my answer machine, and compare their performance to see which one is better.

The World's First Robotic Domestic Assistant

David is 11 years old. He weighs 60 pounds. He is 4 feet, 6 inches tall. He has brown hair. His love is real. But he is not.

A child-sized robot designed for house-sitting and caring for the elderly will go on sale in Japan next month. The robot, named "Wakamaru," has a vocabulary of 10,000 words and can be programmed to watch for burglars or gently wake you up in the morning. Peace of mind and synthetic companionship can now be yours, thanks to Mitsubishi-Heavy Industries Ltd.

More Details about the UAV COS

Larry pointed out some good info to me about the UAV Common Operating System on the DARPA J-UCAS website.

There is a COS FAQ (which unfortunately seems to be more focused on answering Boeing & Northrop's questions about protecting intellectual property than explaining what COS is!) and a Common Systems & Technology presentation which includes a very interesting section on the COS.

Some items of note from the 15.2MB PPT slideshow:

- The COS is more of a POSIX-compliant middleware than an 'operating system,' as it resides on top of an embedded OS.

- Integrates sensors, weapons, communications & control systems to generate decisions and provide a real-time understanding of the operating environment

- Allows autonomous operations, eliminating need for human operators

- Enables accelerated software development... 'best of breed' algorithms shared between platforms (survival of the fittest?)

- Automatic determination of flight path based on mission parameters and threat environment

- Open architecture, non-proprietary source code can be freely used, copied, modified and redistributed

- Initial development timeframe begins Dec 05 and ends Dec 08, with 4 builds planned using a spiral approach

The most significant COS component, in my opinion, would have to be the Discovery/Mediation functionality...

The discovery component provides a set of services that enables the formulation and execution of search activities to locate data assets (files, databases, directories, web pages, streams) by exploitation metadata descriptions stored in and or generated by Information Technology (IT) repositories (directories, registries, catalogs, etc). This also includes the ability to search for metadata semantics to support mediation.

This mediation component provides a set of services that enable transformation processing (adaptation, aggregation, transformation, and orchestration), situational awareness support (correlation and fusion), negotiation (brokering, trading, and auctioning services), and publishing.


What this sounds like to me is a method for storage and retrieval of shared memory resources (by way of metadata [xml?] and semantic analysis), and using those memories to enable adaptation to dynamic situations. That bears a striking resemblance to the way a conscious being uses personal and communal experiences to deal with real-world environments and react to change in real-time. The more I think about it, the more I see the possibility for something truly intelligent to emerge from this architecture. I'm definitely going to have to keep tabs on this project, and if it ends up being open source (as the presentation claims), taking a look under the hood. Now do you understand why I want to work for these people?

Thursday, August 25, 2005

Inside the Mind of a UAV

DARPA is currently developing a common operating system that will serve as the 'brains' for the military's next generation of autonomous systems.

This common platform will allow UAVs to share information and work together more efficiently, and port new advances from platform to platform. Additionally, it will merge inputs from all of the sensor systems to create a single integrated picture of the environment, and interface with the on-board weapons array as well. Could this internal model of the outside world eventually be the seat of consciousness for an intelligent machine? DARPA's own report is not surprisingly vague...

Tuesday, August 23, 2005

Google Tops in Machine Translation

News.com.com reports that Google scored highest in a recent language translation competition run by the U.S. Government.

Google beat out competitors such as IBM and the University of Southern California on the Arabic-to-English and Chinese-to-English translation tests. Interestingly enough, although Google offers an Arabic homepage, Google language tools does not currently offer Arabic translation. Looks like we've stumbled across some more top-secret Google software...

Sunday, August 21, 2005

Smart Cars of the Future

There is a interesting article in Popular Science looking at the future of intelligent systems in automobiles, and how these systems will make transportation by car safer and more efficient.

Highlights from the UAS Roadmap

I've finally had the chance to review the entire Unmanned Aerial System (UAS) Roadmap, and picked out some highlights of interest:

Future UAS will evolve from being remotely operated to fully autonomous system capable of 'self-actualization.' This will require human-level intelligence, specifically pattern recognition skills. The roadmap foresees development of enabling technologies in the 2015-2030 timeframe. (page 52)

Advances in flight autonomy and cognitive processes will allow UAS to move away from remote control by skilled operators towards full autonomy. Several stages of these technologies are reviewed, from remotely piloted vehicles in Vietnam, to high-endurance hand-flown reconaissance systems in the 1970s, to pre-programmed autonomous UAS in the 80s, to Global Hawk today and J-UCAS in years to come. (page D-9)

Several advantages of UAS over manned systems in terms of safety are listed on page F-10:

- Many aircraft mishaps are the direct result of poor decisions by human operators. Robotic aircraft are not programmed to take chances.

- Mishaps from failed life support systems are not an issue.

- Smoke from damaged non-vital systems does not affect UAS in the way that smoke in the cockpit of a manned aircraft does.

- Automated take-offs and landings reduce the need for local training missions, leading to less opportunities for mishaps at home stations. An historical look at UAS in combat is provided on page K-1:

- TDR-1 assault drones flown by pilots via television were used to drop bombs on Japanese positions in 1944.

- AQM-34 remotely piloted vehicles were flown on reconnaissance missions in Vietnam from 1964-1969.

- 18 RQ-2 Pioneer UAS were lost in combat in Desert Storm.

- 26 UAS of various types were lost in combat during the war in Kosovo.

- In the current conflicts in Afganistan & Iraq, combat losses of UAS have been reduced to an average of 2 aircraft per year.

Saturday, August 20, 2005

The Age of Intelligent Machines: The Film

I just came across a old video from KurzweilAI.net called The Age of Intelligent Machines (Real Media).

It was made back in 1987, so some of the specific technologies are dated, but many of the topics are still relevant. One of the more interesting quotes came from Yale Professor Roger Shank, who said "The real problem is not can machines think, but can people think well enough about how people think to be able to describe how they think to machines."

The tech behind Able Danger

All politics aside, an NPR program covering 'Able Danger' and pre-9/11 intelligence (Real Audio & Windows Media) includes a look into the technology enabling the sophisticated data-mining software that allegedly identified four of the Al Qaeda hijackers in the U.S. well before the 2001 attacks.

The Lieutenant Colonel who oversaw the program explains how the smart algorithms sifted through 2.5 terabytes of open souce intelligence looking for patterns in the unstructured data that would lead to terrorists links.

Thursday, August 18, 2005

Automating the Art of War

The Pentagon has just released the latest Unmanned Aerial System (UAS) Roadmap, laying out the development strategy for the next 25 years.

The document is well over 200 pages long, and has plenty of cool pictures. I'm just starting to pour over everything, but here are some of the highlights:

- Name changed from UAV (vehicle) to UAS (system)

- Number one goal is developing unmanned fighters

- 2010: Electronic supression of enemy air defenses (EA-6B)

- 2015: Penetrating deep-strike missions (F-117)

- 2020: Mid-air refueling tankers (KC-10 & KC-135)

- 2025: Air-to-air combat (F-15)

- 2030: Airlift (C-17 & C-130)

- 2030: Air superiority (F-22)

- Roadmap includes detailed specs on current & near future UAVs

I'll post more when I get a chance to dig into this thing further. Addtional coverage is available at DefenseNews.com.

Now if only the DoD took a fraction of the money spent on the F-22 Raptor and F-35 JSF programs and put it towards UAVs...

When the flaw in the software is the human element...

If you read between the lines of the most recent controversy concerning the intelligence failures and the 9/11 commission you'll find an interesting story concerning artificial intelligence and human error.

The NY Post has a piece covering the "Able Danger" data-mining software (registration required) used to identify and track suspected terrorists. It seems as though Able Danger located several of the 9/11 hijackers (including mastermind Mohammed Atta) in the United States well before September 2001. This information, however, was not disseminated or acted upon by intelligence personnel (for whatever reason), and the terrorists were allowed to continue planning their attack. So what we have is software designed to protect American citizens executing its mission successfully, but poor judgement (granted, in hindsight) on the part of the human actors possibly led to the deaths of thousands. Like I've said before, until we become comfortable with fully automated systems making life and deaths decisions on our behalf, society will insist on keeping humans in the loop. This will only change after the human element is repeatedly identified as the single point of failure in the decision chain, and I fear this example will unfortunately be the first of many yet to come.

Wednesday, August 17, 2005

AutoSummary Alpha Release

It pleases me to announce that I have just released the first alpha testing version of the AutoSummary Semantic Analysis Engine under the BSD License.

When completed, AutoSummary will generate contextually-relevant summaries of plain text documents using various statistical and rule-based methods of Natural Language Processing. First, the part-of-speech and specific word-sense (meaning) is determined for each word. Next, each sentence is deconstructed and the subject/predicate/object is identified. A map of relationships between word is then created. From this, specific themes are identified and memes (general ideas) are generated. Finally, the memes are used to create summaries of the original document of varying length and detail.

Currently, only the part-of-speech tagger has been implemented. A JPhrase object is created which contains semantic information about a given phrase of words, including part-of-speech scores and possible word-sense combinations. The part-of-speech tagging method takes the JPhrase and returns a marked-up string with each word in the phrase associated with a tag corresponding to the part-of-speech (noun, verb, adjective, adverb) determined to be most likely used for this particular instance. To make this determination, usage statistics from the WordNet semantic concordance texts are used.

AutoSummary uses the WordNet lexical reference system via the JWords Java Interface for WordNet as its source of lexigraphical information. In order to run AutoSummary, you must first install WordNet 2.0 and edit the JWords configuration file.

This alpha test release is EXTREMELY limited. Support for articles (a, an, the, etc), plurals, tenses, pronouns, and the verb 'to be' has not yet been implemented. If these types of words are entered into the current version, the program will likely crash. The simple demo included in the release is merely intended to show how the part-of-speech tagging system will determine the part-of-speech for each word in a given phrase.

I've been pushing pretty hard over the last week or so to get this initial release out. Once I take a must deserved rest, I will get a publicly available prototype up and running for my wildcard-based general question answering script, go back and add WordNet 2.1 support to JWords, and also take a serious look at setting up a web version of the AutoSummary demo program.

AutoSummary is available for download at SourceForge.net http://sourceforge.net/projects/autosummary

Javadoc documentation for AutoSummary is available here.

Wednesday, August 10, 2005

Wild about Wildcards

The C|Net News Google Blog entry explaining the use of wildcards in Google searches gave me a great idea for another small project.

'Fill in the blank' type questions can easily be converted into a wildcard search. A carefully constructed intermediary process could be used to tap the vast resources of the Google databases to provide real instant answers to straightforward questions. Once I release the initial version of my new semantic analysis engine, I will code up a PHP page that takes user input in the form of a simple English question ("What is the capital of Delaware?"), convert it into an appropriate Google wildcard query (the capital of Delaware is *), capture the output from Google and reformat that output in the form of an answer to the original question. The answers won't be 100% accurate, but it should be a bit more realistic than other attempts at natural language question answering.

Just Around the Corner

The ability to transfer your consciousness to a machine, and therefore live forever, is in our very near future according to futurist and AI advocate Ray Kurzweil.

Rapid advances in artificial intelligence and nanotechnology will even lead to "experience beamers," which will enable one person to receive the total sensory input of another through full-immersion virtual reality. Soon we may all know what it's like to be John Malkovich.

Tuesday, August 9, 2005

JWords Update Release Notice

I am happy to announce that the latest version of the JWords Java Interface for WordNet has been released. JWords 0.2.0 Alpha includes new methods for calculating the relative likeliness that a word will appear as a particular part of speech, which may be used for statistical semantic analysis (like POS tagging), as well as an updated documentation. These features were specifically designed for a forthcoming semantic analysis package... which will be released shortly.

JWords is available for download at SourceForge.net http://sourceforge.net/projects/jwords/

Javadoc documentation for JWords is available here.

Giving Away the Farm

IBM has announced that it will release its new Unstructured Information Management Architecture (UIMA) technology under an open source license for software developers to build upon.

UIMA uses natural language processing and other techniques to analyze and annotate vast amounts of unstructured information, producing relevant knowledge for users to deal with. This will enable the creation of intelligent search engines that can understand the underlying conceptual relationships between documents, as opposed to current systems that focus simply on keywords and hyperlinks. The IBM website for this project seems rather dull at first, but if they can deliver on the capabilities they're promising, we certainly have a lot to look forward to.

Too Bad it's Remote-Controlled

The C|Net News Science Blog picked up a story about a new unmanned ground vehicle currently under development for the US Marine Corps.

Carnegie Mellon University gave its first public demonstration of the Gladiator Tactical Unmanned Ground Vehicle (TUGV) on 4 August. This remote-controlled robot is designed for reconaissance and search & discovery mission in hostile environments, but the military is already looking to expand its capabilities by adding machine guns and other weapons. The latest prototype even includes hand grenades which can be used to clear obstacles (and personnel?). Perhaps the developers could work with CMU's DARPA Grand Challenge team to integrate some autonomous control systems into the Gladiator...

Monday, August 8, 2005

Better Off Without the Butterfly

Despite its questionable track-record of innovation, many people often assume the coming revolution in Artificial Intelligence will be led by Microsoft.

Although MS has devoted significant resources to this cause, my utter lack of faith was recently amplified by this banner ad for MSN Search. In an attempt to showcase the new 'intelligent' instant answers provided by their search engine, MS has demonstrated new levels of artificial stupidity. A definition of champagne (the bubby alcohol beverage) is not a valid answer for a question seeking to ascertain the location of the Champagne region of France. MS is completely missing the point, and I suspect this trend will continue. I'm betting on another couple of grad students defeating the billion-dollar warchest of Microsoft in this battle as well.

Have you ever seen the sun rise ... twice in a row ... three times...?

Paul Graham recently had a very interesting article about what businesses can learn from open source.

The entire piece was very well written, and the author makes a lot of good points, but what captured my imagination the most was the part about the optimal working environment for a programmer. Paul says that people working in the comfortable surroundings of their own home are often exponentially more productive than corporate rats in a stuffy cubicle farm. Based on my own personal experience, I would certainly agree. I find I do my best work in marathon sessions, often involving massive amounts of caffeine and highly irregular sleep patterns. I understand many programmers share similar experiences. Once I get 'in the zone,' as they say, I will work solidly for hours on end paying little attention to time or the world around me. Were I restricted to a structured work environment constantly struggling against interruptions and distractions like co-workers, meetings and email, I fear my programming would suffer.

I am currently working hard to finish up the next release of JWords, as well as the initial release of another semantic analysis tool. I've been trying to complete this stuff for weeks now, but I find the only way I can get anything done is if I rush straight home from work and devote the entire evening to programming. If I decide to go workout, play basketball, see a movie or go out to dinner, and try to pick up where I left off and program a little bit at a time, I never get anything done. By the time I sit down and get going, its time to sign off for the night. My old friend the all-nighter is no longer an option with my responsibilities at work. Usually weekends offer a real chance to get down to business, but I'm afraid my willpower is just barely too weak to resist the temptation of living it up at the beach. But on those rare occasions when I can devote a significant amount of time to this endeavor, and everything is firing on all cylinders, nothing else compares.

Tuesday, August 2, 2005

"Your mama was a snowblower"

I just got back from seeing Stealth, the newly released motion picture about an Unmanned Combat Aerial Vehicle that goes haywire and turns on its allies, and I have to say that it was much better than I thought it would be.

I was anticipating a horrendous bag of shite, but the movie was surprisingly tolerable. The special effects were fun, the story was somewhat believable, and the AI themes were adequate. The story explored our resistance to recognizing intelligent behavior by a robot. our reluctance to trust an artificial entity, and our fear of losing control of or being replaced by a sentient machine. In my opinion, the biggest shortcoming of the film was the sophomoric reliance on a lighting strike to instigate consciousness in the agent. Sound familiar?

Hopefully, with enough R&D money and brilliant engineers we will see the deployment of advanced intelligent systems like these in the near future.

Sunday, July 31, 2005

The Mechanism of Human Consciousness

KurzweilAI.net picked up an article from The Economist about a possible breakthrough in the search for the neural correlate of consciousness.

In his latest (and final) published paper, Francis Crick (the late co-discoverer of DNA) speculates that the neurological basis of human consciousness is the claustrum, a thin layer of gray matter with two-way connections to every region of the cortex. It is possible that the claustrum is responsible for processing all of the various inputs from different parts of the brain to create a "cohesive, conscious experience." If research demonstrates this conclusion to be true, it will unequivocally prove the Materialist view that consciousness is merely a product of a physical system, and therefore can be artificially reproduced by mechanical means.

Rise of the Machine

I finally got around to reading a futuristic Wired article pointed out on Slashdot.

The bulk of the article is a retrospective look at how people have thought about and used the Internet. The really interesting part, however, begins with the last few paragraphs of page 4. While the Slashdot crowd focused on the prediction of a web-based OS and its ability to heal itself, the truly remarkable forecast is the emergence of real artificial intelligence from the net itself. The author recognizes that this "planet-sized computer" is as complex as the human brain, and is growing exponentially. It has already exceeded the "20-petahertz threshold for potential intelligence" proposed by Ray Kurzweil. Our participation in and behavior on the world-wide web might provide this being with the knowledge and programming necessary for consciousness to evolve. In the very near future the human race may be presented with a global network that has become self-aware.

Skynet anyone?

Thursday, July 28, 2005

A Formal Framework for Conceptual-Level Cognition Based on Objectivist Epistemology

I've been doing a lot of research into Objectivist Philosophy lately, and its given me a lot to think about. I've studied philosophy pretty intensely over the past 5 years (including a year at Oxford), and I don't understand how this could have escaped my attention for so long. I think I may have finally found something that encompasses most of the conclusions I've arrived at regarding reality and the existence. If you want to understand my personal view of the universe, Objectivism is unquestionably the perfect place to start. This website, however, is not a 'philosophy blog,' so I will quickly move along to my point.

One component of this philosophy, namely Objectivist Epistemology (the nature of knowledge), has led me to an idea for an internal conceptual model of a conscious machine. This system of knowledge representation would closely mirror the Objectivist structure of concepts and instances. Simply put, Objectivism contends that the senses are the only source of valid information, that 'reasoning' is nothing more than the classification & organization of the information provided by sensory perception, and that consciousness is the act of transforming that information into a system of concepts and propositions consisting of knowledge about the world. A conscious mind creates concepts by identifying and generalizing similar characteristics of things it encounters through the senses. Once a concept has been formed, an unlimited number of instances of that concept can be recognized by the agent.

This framework immediately reminded me of object-oriented programming, with concepts acting as classes and instances as objects. Just as a programmer can construct an unlimited number of objects once its class has been defined, a conscious mind can recognize endless instances of 'airplane' once the concept of 'airplane' has been properly formulated. The key is to identify the relevant characteristics that define the concept (man-made machine, has wings, enables flight), and to recognize those characteristics in similar phenomena.

We could implement this framework in a machine using these steps:

1. Define the machine's sensory perception. How will it observe the world? Will it have eyes? ears? tactile sensors? The limits of its perception will directly affect the scope of the machine's conceptualization.

2. Construct the mechanisms for input/output. Connect the cameras and microphones that serve as eyes and ears, and provide the machine with some method to interact with or otherwise manipulate its environment.

3. Formulate the aforementioned conceptual framework. Write the software that controls the operation of these devices, analyses the data they collect, and classifies & organizes the information accordingly.

4. Release into the environment. Allow the machine to observe and interact with its surroundings, building concepts and collecting knowledge about whatever it can discover.

For example, a machine designed with these capabilities might one day encounter what we would recognize as an 'airplane.' First, the machine would compare this object to its memory files to see if it had encountered something similar before. Failing that, it would make note of the distinguishing characteristics of the object and assign it an arbitrary identifier. Later on, when confronted with another instance of an 'airplane,' the machine would recognize distinct similarities between this object and the unidentified one in its memory, and would construct a concept of 'airplane' based on the obvious relationships between them.

This framework doesn't solve some of the major challenges of artificial intelligence like pattern recognition, machine vision or natural language understanding, but it does provide us with a system to integrate these systems once they are accomplished. And it wouldn't do much good starting from scratch. This agent would require some background information, a 'seed of knowledge' if you will, in order to get up and running. Even if this included things as (relatively) simple as language skills or a basic means of communication, designers will need to provide the machine with a small amount of starting information in order to 'prime the pump.' Humans are born with many 'instincts;' artificial minds like these must be programmed with them. Additionally, we will need to sort out the details surrounding memory access and storage requirements for this agent to function efficiently. An intelligent system which maintains a full audiovisual record of its experiences would likely be impractical, so perhaps this is where some contextually-relevant summary software would be useful.

Tuesday, July 26, 2005

Is It Even Possible?

I was recently introduced to an intriguing speech on the plausability of conscious machines given to a club of Objectivists a few years ago.

I appreciate many of the author's positions, but am not sure what his ultimate message is. The simple fact is that we are trying to recreate consciousness when we don't even know what consciousness is! Some attribute it to the soul, which doesn't address the issue and is simply an appeal to superstition. Others argue that thought is nothing more than calculation, but that fails to account for comprehension and understanding. Even though we are unsure of the direction we are going, we continue in our endeavor to build a thinking machine. In the end, perhaps our greatest success will not be the accomplishment of that goal, but in fact that we discovered the true nature of our own consciousness along the way.

Monday, July 25, 2005

A Tiger Under the Hood

Slashdot pointed me in the direction of a PCWorld.com article about yet another DARPA Grand Challenge team. Unlike the rest of the 40 semi-finalists, this group uses Mac OS X to control their vehicle. But it seems they stole Stanford's idea to use a VW Taureg as the platform.

Wednesday, July 20, 2005

David Beckham's Modeling Contract Safe For Now

I don't normally pay much attention to this sort of thing, but C|Net News is covering RoboCup 2005, and it looks like we've got some real progress in the field of soccer robotics. Over the next several years we might even see some of these humanoid bots achieve 100% autonomy.

Against (Artificial) Intelligence?

Kuro5hin has an interesting (if amateurish) op-ed piece critical of the entire premise of AI.

Among the main points are that AI has yet to produce anything useful (and is therefore worthless), that machine consciousness is impossible, and that we should completely discard the philosophy of mind. I, however, would I argue that hashing out the philosophical issues is essential to solving the problem of AI. Indeed, the creation of a truly conscious machine will require collaboration between brilliant individuals from several disciplines, among these being neuroscience and philosophy, in addition to computer science.

Although I disagree with the author's premise, believe his view of AI is very limited, and find his logic fundamentally flawed (tons of circular reasoning), the article is worth a look, and has stimulated a lively discussion. I particularly appreciate the comment that says if the author's logic was applied to the early days of aviation, he would have to slam "the Wright brothers because they didn't achieve supersonic flight."

Tuesday, July 19, 2005

Translating and Sorting 2D Arrays for Fun

Just a quick project update. Yesterday, I succeeded in making my probability algorithm much more efficient, vastly reducing the number of wasteful steps and minimizing the memory footprint. Then, tonight, I straightened out the sorting functionality for the results using Arrays.sort(Object[] a, Comparator c). Next up, I want to write something that will generate a 'confidence level' number to accompany the results. After that, I will clean up all the code and put it in a presentable format for you all to see... I swear!

Robotic Camel Jockeys Save Enslaved Children

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.

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.

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.

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.

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...

Thursday, July 14, 2005

It Knows...

That's what I said to myself while working on my project tonight.

Work was really slow today, so I had some time to scrutinize the probability algorithm for my part-of-speech disambiguator. Basically, the tool I'm working on now is meant to correctly identify the part-of-speech for each word in a given phrase. When I got home and tinkered with the code a bit, I was astonished with how well it worked. The program is now analyzing all possible combinations, and reports the instance it determines is most likely to occur, based on general usage statistics.

When I realized it was doing what I hoped it would do, and the statistical formula was working properly, I was pleasantly surprised. Later on, I will combine this with other methods of semantic analysis in an attempt to determine the specifc meaning of each word in a sentence. But for now, I'm cleaning up the code a bit, and improving the performance by eliminating unnecessary steps. The algorithm is working... but its slow, with an efficiency on the order of O(4^n)! Once I speed it up and get it into a presentable format, I will make it available to download and try out.

Not exactly what you would call a 'Eureka!' moment, but I was pleased nonetheless.

Wednesday, July 13, 2005

Pink Slip for NASCAR Drivers?

C|Net News reports a Carnegie Mellon Robotic Vehicle successfully completed a 200 mile, seven hour drive, completely autonomously.

Although the course was merely 131 laps around a 1.5 mile racetrack, the duration of this event represents a significant milestone in the development of driverless vehicles. The next step will be the 2005 DARPA Grand Challenge. The Carnegie Mellon team led all participants in last year's contest, completeing 7.3 miles of the 142 mile course before getting stuck.

Tuesday, July 12, 2005

Ethics & Artificial Intelligence

Right now I'm listening to a very interesting radio talk show about the IBM 'Blue Brain' Project and the ethics of creating a conscious machine.

You can listen to the RealAudio stream here.

Fighters without Fighter Pilots

Popular Science has an in-depth article about the possible future of air combat.

It discusses the development of Unmanned Combat Aerial Vehicles (including the X-45 Stingray), their roles in future conflict, and some of the internal politics related to the project.

Monday, July 11, 2005

Let the Buyer Beware!

I came across an interesting news story today that made me think. Basically, some store in Canada accidentally sold a few copies of the new Harry Potter book more than a week before the official release date. Yawn. But what's interesting is that the book's distributor won a court injunction "barring the buyers of 'Harry Potter and the Half-Blood Prince' from disclosing the plot." Additionally, the court ordered all copies be returned to the distributor.

This means that some poor Canadian child could have walked into his local bookstore and purchased a book he'd been waiting years for, but because the corporation behind the book decided it had been accidently sold a bit too early, a court of law decreed it must be returned and the little hoser has to keep his mouth shut about the storyline. I didn't know Canadian law granted merchants the right to refuse a transaction after the fact, or could restrict the freedom of speech to preserve marketing hype.

Could this be another step towards The Right to Read?

Sunday, July 10, 2005

My First Mac

So I finally broke down and bought the Mac mini I'd been eyeing for several months now. I originally planned on buying it as soon as I returned from my trip to Mississippi, but hesitated because of the WWDC-announced migration to Intel CPUs. But since I was eager to set up my 'Media Center Mac' I decided to go ahead and get the damn thing.

I drove up to the Apple Store in the Christiana Mall because I don't like waiting for shipping and the store has a nice military discount. To get the most out of the mini as a media center computer I elected to go with the so-called 'ultimate' package. Basically that's the mini with all the options: faster CPU, more RAM, bigger hard drive, SuperDrive, Bluetooth, Airport, yada yada...

Mac mini 'Ultimate'
1.42GHz PowerPC G4
512MB DDR333 SDRAM
80GB Ultra ATA drive
4x SuperDrive (DVD±RW/CD-RW)
Internal Bluetooth + AirPort Extreme Card

After the discount, that came out to $795 (no sales tax in Delaware). I added an Apple Wireless Keyboard & Mouse set for about $100 more. They were also offering $100 off any printer with the purchase of a Mac, so I picked up the HP PSC 1610 All-in-One ($29 after rebate).

So far, I'm really happy with it. As I expected from Apple, it was very easy to set it up out of the box. The only difficulty I came across was getting it to look right on my Samsung 32'' DynaFlat HDTV. I had to buy a DVI cable from Best Buy on the way home ($49), but I had a hell of a time getting the settings right. Maybe it had something to do with the fact that this model HDTV is not 16:9 widescreen, but I finally got it working on 720 x 480.

Connecting it to my home network was a breeze. I transferred all of my music and photos over from my laptop into iTunes and iPhoto. I've used iTunes for Windows before and I've always liked it. iPhoto, however, feels a bit clunky to me. It won't let me organize my photos the way I want to, but maybe I'm just not familar enough with the program yet or OS X doesn't like my hierarchical way of thinking.

Since then I've been going download-crazy, grabbing tons of cool videos from GrouchyMedia.com and QuickTime movie trailers. Video plackback quality is excellent on the HDTV- exactly what I was hoping for.

I haven't used a Macintosh regularly since before Windows 95, and I have to say I am as impressed with OS X Tiger as I thought I would be. Finder is so fast its scary. Safari is ok, and its growing on me, but I might just have to try out Firefox for Mac. The interface is simple yet beautiful, but I'm going to have to get used to only having the one mouse button. All in all, OS X lives up to my expectations and I'm eager to tinker around with it.

All in all, the Mac mini has integrated nicely into my home theatre. I wanted to be able to watch videos, browse photos, play music and surf the web on my TV while sitting on my couch with a wireless keyboard and mouse, and the Mac mini does all these things very well. Not a bad little setup for less than $1000.

Now I just have to figure out how to watch TV and use the Mac at the same time...

Sunday, March 13, 2005

Natural Language Processing in the Global War on Terrorism

I came across a NY Times article recently discussing software used by the CIA to scour the web for terrorist messages.

The company behind the sofware, Attensity Corporation, has developed tools which can take the near-infinite masses of unstructed data on the Internet, and turn it into meaningful information. They've developed algorithms that can parse sentences, extracting the subject, object, verb, etc. enabling the computer to process the plain text and take contextually relevant actions.

This type of software, teaching a computer to read and extract read information from text, is exactly the sort of project I have in mind. I guess all those grammar lessons spent diagramming sentences in elementary school were actually important.

Wednesday, February 23, 2005

JWords Alpha Release

I am pleased to announce that the first alpha testing version of the JWords Java Interface for WordNet has been released under the BSD License.

JWords is a simple and easy to use Java interface for the WordNet 2.0 command line tool. It provides classes and methods to create and use JWord objects containing the information stored in the WordNet lexical reference system.

I created JWords because I wasn't happy with any of the other Java APIs available for WordNet. I plan on using WordNet as the primary lexicon for autosummary software I am creating, and I needed to create a custom-tailored interface to suit my needs. By treating words as objects, and using the WordNet command line tool to handle the burden of reading the database files, JWords offers a simple and versatile way to access a wealth of lexical information.

JWords is available for download at SourceForge.net http://sourceforge.net/projects/jwords/

Javadoc documentation for JWords is available here.

Monday, January 31, 2005

Teaching Computers to Read

While trailing far behind in skills such as long division, the average three year old human is a much better reader than even the most sophisticated computer program. But for how long?

Two professors at RPI are working on software that can read text and answer questions based on the relevant information. They hope to one day develop a system which can analyze and act upon real-time information "by either reading or listening to spoken instructions."

The difference between these guys and me? They've got a sweet grant from DARPA.

Saturday, January 29, 2005

Semantic Knowledge from Google

Again, people out there are stealing my ideas. Where the heck did I put my tin foil hat?

As posted on Slashdot, a team in Amsterdam is working on an unsupervised system that can perform Automatic Meaning Discovery Using Google. This is quite similar to the idea I have of building a much more broad and extensive knowledge base for AIML bots using a web crawler with built-in semantic analysis. Except these guys are limiting the scope of their project to distinguishing "between colors and numbers, and [...] 17th century Dutch painters."

Wednesday, January 19, 2005

Mac mini TV

That new Mac mini has got the wheels in my head spinning. I think if I hooked it up to my HDTV it would make for a pretty sweet media center computer.

I had been thinking about getting a Mac for a while. I've toyed around with OS X a bit, and I'd really like to get to know it inside and out. At the same time, a lot of my friends have been setting up dedicated media center PCs, and I was considering following suit. Now I just might be able to combine both ideas into one.

I can run a DVI cable from the Mac mini to my Samsung HDTV. Add the optional internal Bluetooth module and wireless keyboard & mouse, and I'll be able to have a great OS X experience on a 32'' screen from the comfort of my sofa.

1.25GHz Mac mini: $499
Bluetooth add-on: $50
Wireless keyboard & mouse set: $99
DVI cable: $99

Total cost: $747

I should be able to swing that no problem, but I think I'll wait until 'the first half of 2005' for Mac OS X v10.4 Tiger before I take the plunge. I'm still planning on building the RAID 1 development platform for the project, but that's on hold for now while the paychecks roll in and the prototype software comes together.

Tuesday, January 18, 2005

I guess this makes me a pro?

Finally got a chance to write (well, edit actually) some code at work today. Besides some freelance web design I did a while back, this was the first time I was paid for programming.

In all reality, it really wasn't that big of a deal. Last week, I was asked to take a look at some PHP for a web interface to a pretty high-profile database we use. There was a bug somewhere that was generating incorrect entries. Today I got a chance to poke around in there, and I quickly isolated the problem and wrote a very elegant fix if I do say so myself.

I showed it to the database administrator, and she was visibly excited when she realized it was working properly. Now she won't have to go in and manually edit every single new entry.

I showed it to my supervisor, and he was pretty impressed. He doesn't have much experience in this area, but he had had another CS grad working on the problem for at least a couple of weeks, to no avail. When I showed him exactly how simple my solution was, he remarked that the other guy will be kicking himself when he sees it.

I honestly didn't think it was that I did anything special, but I certainly impressed a few people. What I did fixed an annoying problem in a pretty important system we use. Hopefully, this will lead to more oppurtunities for me to work directly on projects like this in the future.

And besides, it's pretty sweet to think that code I helped to write is running on a military system. :)