January 2003

        

AI Expert Newsletter

AI - The art and science of making computers do interesting things that are not in their nature.

January 2003

Business Models for Deploying AI

There is no doubt of the benefit of various AI tools and techniques, but, compared to conventional applications, there are additional costs associated with using AI. In other words, deploying AI requires a cost/benefit analysis just like everything else.

The major cost is acquiring the people with the necessary skills. AI techniques are not that difficult to learn and use, but they are different and take some time to learn and master. The benefits of a potential AI application must outweigh the costs of dedicating the people and training time necessary to get the job done right.

Last month's newsletter covered two models of favorable cost/benefit analysis for deploying AI. Both involved large organizations with 1) the financial resources to invest in people with AI skills, and 2) a significant body of potential applications that made the investment worthwhile. One was a large corporation, American Express, that developed staff for internal development; the other was the Egyptian Department of Agriculture, which used a cooperative effort between government, academia and commercial agriculture.

This month covers a third cost/benefit model that does not require large financial resources, but instead requires individuals willing to take a risk in the free market. It is the small company using AI to gain a competitive advantage in narrow application markets.

In these cases, the company's investment in AI will hopefully be compensated for by multiple customers of that company's products and services.

The key to success for this model is knowing how to market the products. Typically, however, this is not that big a problem, as the entrepreneurs involved understand the problems of the market because of personal experience.

That is the case for the three examples which follow: a company that knows the education market providing classroom scheduling; individuals with experience in pharmaceutical research providing data mining tools and services; and developers of sophisticated military simulations moving into computer game software.

These three examples came from following threads of interest from readers, so keep those e-mails coming.

Classroom Scheduling

Antinoos is a Greek company with a handful of application products targeted at specific applications. Orologio is their school time table application. Scheduling applications, such as school time tables, are notoriously difficult (see scheduling link). Antinoos has implemented their own probabilistic weighted search scheduling algorithm in the application, developed using Borland's Delphi 3.

Antinoos and Orologio provide a perfect example of how a small, technically-oriented company can make an investment in AI technology and apply it to applications for users that have no interest in how the application actually works. ("People want holes, not drills." -- Black and Decker)

This model is more applicable today than ever, due to the Internet's phenomenal potential to reach Global markets.

In the words of Haris Saravanos of Antinoos: "There are so many fields to use AI and create software for real business, but so little time. Of course, for some years markets (U.S. Market excluded) were unable to follow. Thanks, basically to Internet, things have changed. Nowadays we're in process of selling OROLOGIO in markets such as BOTSWANA's !! Greek software (or any kind of product) in Botswana was out of the question a couple of years ago."

Pharmaceutical, Biotech Data Mining

Pharmaceutical and biotech companies produce tremendous amounts of experimental data. SciNova Informatics is an Indian company that specializes in data mining products and services that provide researchers with clearer insights into that data.

They use a variety of techniques, including automatic rule induction, neural networks and genetic algorithms. They provide both consulting services and a commercial product, Prometheus.

Like Antinoos, they started their initial work with hospitals and companies in India. They are branching out to Europe and the U.S. Their product lines are developed in conjunction with their consulting work.

Game Simulations

Stottle Henke Associates is a growing company offering, among other products, tools for creating intelligent agents in virtual world computer games. In their case the products are a result of extensive contract work they did generating intelligent tutors and training simulators for the military.

Like SciNova, their company provides both consulting/contract services and products related to those services.

The gaming product is called SimBionic(TM). The product fits this newsletter's general model of AI. There is an engine that implements the agents, and a graphical development environment that lets game developers easily create the agents and their behaviors. The graphical development environment lets subject matter experts directly program the behaviors without an intermediate programmer. The engine is written in C++ with an API that let's it be easily integrated into a larger gaming context.

Spiritual Machines

If you haven't already read The Age of Spiritual Machines, by Ray Kurzweil, I highly recommend it. I won't guarantee that you'll like the book, although you might, but I will guarantee that it will make you think. His thought-provoking prophecies of digital circuitry eventually replacing human brains has triggered many different responses, many of which are posted on Kurzweil's site.

Kurzweil has a tremendous resume of success. He got his start following the entrepreneurial business model. He used his inventive genius to create optical character recognition and speech synthesis tools, and then his marketing genius to understand and reach the blind market with his reading machine for the blind. This led to meeting Stevie Wonder, which led to music synthesizers, which led to... Well that whole story is in the book as well.

Without even looking to the future, his accounts of what is happening in the present are fascinating, and well documented with extensive references. And he lays out a blueprint on how to build a brain today.

It's simple. Just combine recursive problem solving with evolutionary algorithms that optimize neural net topologies.

Interesting. That's kind of what the developers of programs to play the game of go are doing.

Go and Computers

Go is considered by many who have played it to be the ultimate board game. It has fascinated players for centuries, yet today it has an added charm. The best computer go programs are only at beginner levels. One can feel smug playing a game that artificial intelligence cannot, at least for now, play.

Why is that? It's not for lack of trying. There is an ongoing assault of very talented go players and programmers trying to create better and better go programs.

One reason is simply the size of the board. It's played on a 19x19 grid so there are more moves to consider, which means standard alpha-beta search algorithms have much more work to do.

But that's not the main reason. It's very difficult to assess how good a move is. In fact, it is extremely difficult to simply write a program that correctly determines the score at the end of a game, a feat easily carried out by human go players.

How is that evaluation done? It's a pure and simple human brain pattern-matching exercise. The complex interrelated patterns of white and black stones hold the key to understanding the game.

Which is all kind of ironic. Chess programs started out looking to emulate human pattern matching, and instead evolved into muscular search programs that overwhelm human intelligence. Go programs are going the other way. Search simply doesn't work, and developers are looking to emulate human pattern matching, as Kurzweil describes.

When a computer finally does start playing reasonable go, it will be doing so in a more human-like way than its chess playing cousins.

See the links for information about computer go.

Basketball Scheduling Experiences

A number of years ago I was contacted by the Atlantic Coast Conference (ACC), one of the top collegiate athletic conferences in the U.S., with the problem of generating a "fair" basketball schedule. It appears that college basketball, in the top conferences, is a particularly difficult scheduling problem, due to a very compact season and the desire of each team to not yield any competitive scheduling advantage to other teams, like having less home games on weekends and therefor fewer games with the advantage of a boisterous partisan crowd.

I was told that a scheduling expert had told them the constraints were impossible to satisfy, which had the effect of making it somewhat of an obsession for me.

We did come up with a good schedule for the ACC that year, and have since done other work for other conferences. The Big East Conference men's basketball schedule is considered the most difficult, due to complex arena constraints that other conferences don't have. The individual responsible for the schedules is an avid chess player who spends months manipulating tokens representing teams and games. The ACC told the Big East about our program, but the Big East was skeptical. So just like in the old folk song about John Henry competing with the steel-driving machine, it became a head-to-head competition. Well, I think it was a tie, but they liked the hand developed schedule better.

We still schedule the Big East women's basketball each year, which doesn't have the arena constraints. But we've never truly gotten a program that we like, so we keep changing it.

The first version of the program, written in Prolog, used a pure depth-first search, and produced great schedules when the constraints were solvable, after considerable searching. The order of the initial list of games to be scheduled had a tremendous affect on the program's success or failure. Given the wrong start, the program never converged, but with a good start it might converge relatively quickly. This immediately led to the "I'd rather be lucky than good" rule that shuffled the input list and restarted the program after it had run too long.

It also suggested genetic algorithms as an approach. The next version of the program was a pure Java genetic scheduling algorithm. It had the advantage of generating poor, but playable, schedules early on and then gradually evolving better and better schedules. It worked, and was less nerve-racking than the first version, but it never found the really great schedules the first version did. And it also took a long time.

The problem with genetic algorithms is that, despite a really cool name, they are just hill-climbing algorithms. They incrementally move a little higher in the evaluation function's space each time. And like all hill-climbing algorithms, they might be going up a minor summit, rather than Everest. And it appears the search space of the basketball schedule is a very rugged irregular terrain. Again, luck in the start turned out to be key.

Which makes one wonder about Kurzweil's vision. He has one sentence in his book, where he notes that you need to have a good random sample of starting points for evolutionary algorithms to work. Is evolution really such a great means of finding solutions? Doesn't it really just find some local summit near the starting point and sit there?

And what does this mean about human intelligence? Are we evolving up some minor peak? Might not the reptiles have done better than us mammalian types if they hadn't gotten in the way of a big meteor?

Back to this human intelligence wrestling with basketball schedules. The latest and current version uses a combination of Prolog search with C++ classes representing individual team schedules. The C++ code can quickly generate evaluation functions scoring each team's schedule. That score becomes the single constraint driving the search. Recursion repeats the scheduling process by using the last best score as the single constraint for each succeeding schedule. And it still shuffles the input stream each time looking for a bit of luck.

It works better than the first two programs, but still takes a long time. I haven't yet tried using any of the constraint-based languages or tools. Maybe this year I'll have time to try out Mozart, which has built-in constraint handling, and a classroom scheduling sample.

Any and all reader feedback on this application is welcome.

Erratum

Thanks again for your feedback. One reader pointed out that the Saarland University is in Germany, not Denmark. My apologies, and to think, a recent news article reports that on a simple geography test, U.S. students are among the worst in the World. Sigh.

Links

The Best of AI Expert

AI and Locomotion: Horse Kinematics [Jan 94 pg 18] - Patti Koenig and George Bekey describe a University of Southern California research project that lets a rider sit on a mock horse and control a virtual horse for the complex gaits of dressage. Neural nets are used to transmit the riders inputs to the horses movements, but unfortunately aren't described in much detail. However the complexity of dressage, which I never understood, is explained as well as the overall architecture of the project.

Gravitating Towards Common Sense [Feb 94 pg 9] - Lance Elliot discusses the advantages of including strategic metarules in a rule based system. The metarules determine the best reasoning strategy the system should use, based on the particular case being processed. Given that different problem domains have both different specific rules and different ways of strategically approaching a problem, understanding a domain's metarules is often the key to successful deployment of a rule based system.

Using Neural Nets to Manage Investments [Feb 94 pg 16] - Dean Barr and Ganesh Mani describe the use of neural nets for forecasting financial markets. This is an excellent introduction to the basic problems and approaches used. The article also discusses ways to deal with the major shortcoming of neural nets, which is their inability to "explain" themselves. Sensitivity analysis is used to determine the effects of various input parameters; rules are then generated based on that analysis. Good stuff.

Scheduling

A State-Of-The-Art Review Of Job-Shop Scheduling Techniques - Anant Singh Jain and Sheik Meeran provide a very technical review of scheduling techniques, from the earliest systems to the most recent, covering techniques such as Tabu Search, Genetic Algorithms and Simulated Annealing. The job shop domain is used as a classic example for scheduling bench marks. Read this article to get an appreciation for the difficulties of scheduling applications and further pointers on research using the various techniques.

Go

Computer Go - David Mechner's computer go page has two excellent articles on the subject. The second one listed on the page is shorter, but the first, All Systems Go, has more in depth analysis and interesting rambles on one player's path towards excellence in go.

The American Go Association - Has links and introductory material for those interested in learning the game, including a number of sites that support online play. Warning -- the online sites are addictive and contributed to this newsletter missing its deadline.

 
Copyright ©2002-04 Amzi! inc. and CMP. All Rights Reserved.