February 2003

        

AI Expert Newsletter

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

February 2003

Robotic Soccer

The Robocup goal: By the year 2050, develop a team of fully autonomous humanoid robots
that can win against the human world soccer champion team.

While computers are winning at chess, the Robocup organizers are looking to win at soccer. So far the robots are just playing each other, but the events are getting huge. Last year's event in Fukuoka-Busan drew 188 teams from 29 countries.

There are a variety of competitions, including small, mid-sized, four-legged and human. The small competitions have five robots on a team and can use wireless communication with an off-the-field computer for control. The mid-sized and four-legged competitions require each robot to carry all of its hardware with it.

They also have a simulation league, which is RoboCup without the actual robots, running in a simulator instead.

From Sony's 'old' Web site: "In order for a robot team to actually perform a soccer game, various technologies must be incorporated including: design principles of autonomous agents, multi-agent collaboration, strategy acquisition, real-time reasoning, robotics, and sensor-fusion. RoboCup is a task for a team of multiple fast-moving robots under a dynamic environment."

So, not just a robot doing a task, but a team of robots working together. One of the teams was proudly proclaiming that they were the first to successfully pass the ball in competition. A lot of the research is going to figuring out the opponent. Vision and learning together are a key technology, with the idea being to figure out and learn an opponent's behavior so as to best out play it.

A Google search on RoboCup reveals the scope of the international research going into the event. Universities from all over the World have Web sites describing their robot teams, technology and research.

With all this activity, it seems likely they might reach their goal. See the links for more details.

AI Companies

Here are some more stories of small companies, using AI in specific product niches.

Evolution Robotics

Evolution Robotics provides consumer robotics kits for the home hacker. Their ER1 has gotten a lot of favorable press coverage lately as a hobby robot. They provide the mechanical framework, the sensors and the software, and you provide the laptop. They have recently announced the ER2.

They also provide their technologies to other companies interested in developing commercial robots. These technologies include the Evolution Robotics Software Platform (ERSP) and modules that support robot vision recognition, mapping and navigation, and human-robot communication.

Their origins are more entrepreneurial than other companies we have covered. Their founder is Bill Gross who is also CEO of Idealab. Idealab is a management umbrella that operates a number of high tech companies, providing business and marketing expertise to those companies.

For more information see http://www.evolution.com and http://www.idealab.com

iRobot

iRobot is a start up made of people from, and in charge of, the MIT Artificial Intelligence Lab. It's been in business for 10 years, with the goal of producing robots that are commercially viable. Their products range from toys, to household appliances, to robots for the military.

Roomba is a robot vacuum cleaner that you can purchase through Brookstone for $199. There is a Yahoo discussion group of Roomba users, and other than complaints of the length of battery charge, they all seem pretty happy.

For the military, they have PackBot. PackBots saw action in Afghanistan, doing the dangerous work of exploring caves in the region. The military would rather risk robots than soldiers for this sort of work. I wonder if that will be the case in the world of Kurzweil's visions?

See www.irobot.com for further information.

FriarTuck

FriarTuck is a startup in Singapore focusing on scheduling applications. Martin Henz, one of the principals in the company, was involved in the design and development of the Mozart constraint-based programming language, mentioned in previous newsletters. Not surprisingly, FriarTuck uses Mozart to implement their scheduling systems for health care, education and sports organizations.

Singapore provides excellent support for start up companies, and FriarTuck received its initial funding in the form of awards from business plan competitions. Their first customers are in the Singapore area, but they're outlook is global. Given the impressive results they have produced with the ACC basketball schedule demo, it seems they have a lot of potential.

See www.friartuck.net for further information. (www.friartuck.com looks like a very nice resort in New York's Catskill mountains.)

Basketball Scheduling Continued

Readers of last month's newsletter article about basketball scheduling, pointed me to additional work on the Atlantic Coast Conference (ACC) basketball scheduling problem. It seems it has become somewhat of a benchmark after publication of George Nemhauser's and Michael Trick's article on using integer programming and enumeration to find a better, quicker solution than we did. Theirs still took 24 hours, but it was able to search the entire solution space, something we were not able to achieve.

ILOG, a company offering constraint technology tools, and FriarTuck both have implemented versions of the ACC scheduling program as marketing demonstrations.

FriarTuck is implemented using Mozart, which has popped up before in the newsletter. The most fascinating aspect of their solution is they claim to be able to search the entire solution space in less than a minute. Wow.

One of the main reasons for the speed of the constraint based approaches is simply a better algorithm for tackling the problem. Instead of looking directly for a schedule that works, they break the problem into three phases. This has the tremendous benefit of allowing follow on phases to not waste time evaluating constraints that were incorporated in generating earlier phase results.

The first phase searches for acceptable patterns of home and away games, without regard to any other constraints, or individual teams. Once those patterns are found, they are enumerated and a universe of possible schedule patterns emerges. Those patterns are then filled in with generic team place holders, searching for possible generic time tables. The time tables are then filled in with actual team constraints in the search for final workable schedules.

See the links for the various articles, as well as Michael Trick's summary page of all sorts of sports scheduling services and products. The articles contain additional references to a host of other sports scheduling research.

Links

The Best of AI Expert

Mining for Financial Knowledge with CBR [Feb 1994]- Paul Buta of Dun and Bradstreet describes the use of case-based reasoning (CBR) to mine knowledge from financial data. The article has excellent coverage of both the problem domain and the primary issue with CBR systems, which is determining the relevant 'cases' are and how best to represent and store them.

Scheduling Space Shuttle Missions: Using Object-Oriented Techniques [Mar 1994] - Andrea Henke of Stottler Henke (mentioned in last month's newsletter) describes a planning and scheduling system designed for the multi-year process a putting a shuttle in orbit. The system uses rules, objects and scheduling algorithms to capture the expertise of the shuttle planning experts. It's an excellent case study of applying a variety of AI and programming technologies towards the solution of a complex problem.

Dynamic Hill Climbing [Mar 1994] - Michael de la Maza and Deniz Yuret, both of MIT's Artificial Intelligence Laboratory, describe this search algorithm that incorporates genetic algorithms with more conventional mathematical optimizations. By incorporating both strategic and tactical aspects in the search for a summit, they address the problems mentioned in a previous newsletter about the difficulties in finding maxima in irregular terrains.

Sports Scheduling

The Atlantic Coast Conference (ACC) basketball scheduling problem, mentioned in the last newsletter, turns out to be somewhat of a scheduling benchmark.

http://www.amzi.com/articles/acc_basketball.htm - The original article describing the Prolog program and constraints used to solve the problem. This version took 1-2 days to converge on a solution, but the solution perfectly matched the constraints given.

http://mat.gsia.cmu.edu/acc.pdf - George Nemhauser and Michael Trick's article on using integer programming and enumeration to find a solution, faster and more reliably. This version took 24 hours to find all solutions.

http://www2.ilog.com/oplmodels/display.cfm?ID=5 - ILOG's demo application that solves the ACC schedule problem using their constraint programming tools.

http://www.comp.nus.edu.sg/~henz/publications/#acc.abstract - Friar Tuck's description of their finite-domain constraint program, written using Mozart, to solve the problem. This version takes a minute or so to find all solutions.

http://mat.gsia.cmu.edu/sports/ - Michael Trick's summary page of various sports scheduling packages and services.

Other Scheduling

http://www.npac.syr.edu/users/paulc/papers/patat97/paper.html - Saleh Elmohamed, Paul Coddington, and Geoffrey Fox of Syracuse University describe annealing techniques for university timetabling problems.

RoboCup

http://www.robocup.org - The home page for RoboCup, with lots of information about events.

http://www.csl.sony.co.jp/person/kitano/RoboCup/RoboCup-old.html - This is labeled the 'old' site, but the new one isn't available yet. Lot's of good information on this one, but some of the links are broken.

http://www.csl.sony.co.jp/person/kitano/RoboCup/papers.html - A list of papers about RoboCup and the technologies used. Vision and learning are key topics for building a robot soccer player. The key problem is dynamically learning the opponents moves and how to counteract them.

http://sserver.sourceforge.net - There are a number of mentions of software simulators for RoboCup. This is one of them.

http://www.techfak.uni-bielefeld.de/ags/wbski/3Drobocup/3Drobocup.html - A three-dimensional simulation of robots and RoboCup.

http://news.nationalgeographic.com/news/2002/06/0617_020617_TVrobots.html - Some good photographs of robot soccer from National Geographic.
Copyright ©2002-04 Amzi! inc. and CMP. All Rights Reserved.