IndiGolog: A Programming Language for Cognitive Agent

by Yves Lespérance and Hector J. Levesque

You have just arrived at the office. In a few minutes the office robot should bring you your morning coffee. It will have noticed your arrival from your logging in to the office's computer system. It will also bring you the airline tickets that have arrived in the mail. You got those with the help of your automated travel assistant agent.

In the not so distant future, we can imagine situations where people interact routinely with agents or robots that are fully automated and that make reasoned decisions for themselves about what to do. Likely this will first involve tasks that people find tedious such as filtering email, making travel arrangements on the web, or doing housework. To build an agent that can act intelligently and help a user carry out tasks like these, we need to provide the agent with reasoning capabilities that support building plans of action, explaining its observations and updating its knowledge, predicting the behavior of other agents, communicating and cooperating with them, etc.

For more than a decade, researchers from the Cognitive Robotics Group at the University of Toronto (under the leadership of the late Ray Reiter), together with collaborators at York University, and universities in Rome, Aachen, and elsewhere, have been developing a unified reasoning framework based on a simple logic of action, called the Situation Calculus, for specifying and implementing such intelligent agents. This approach involves first specifying in a declarative way the effects of the actions that can be performed in an application domain (eg, obtaining a coffee from a coffee machine) in this framework. Once this has been done, one can write complex high-level control programs for the agent in terms of these domain-dependent actions (eg, for delivering coffee to people around the office). For this, a programming language called Golog was developed. Golog (which stands for Algol in Logic) looks a lot like a standard procedural programming language. But, the interpreter for this language uses the declarative specification to reason about what the effects of various possible actions would be. The programmer writes a program that can be sketchy and nondeterministic, and the interpreter automatically figures out a way to execute it successfully. The program can be quite vague, specifying only the goals to be achieved, or more detailed, specifying some steps and search control information, or fully detailed, specifying the agent's behavior completely. Later, an extended language called ConGolog was developed to support concurrent high-level programming. This facilitates the design of agents that have both reactive and proactive behaviors.

More recently, we have focused on extending the framework to support the design of agents that operate with incomplete information and acquire new information through sensing actions. A new extended programming language called IndiGolog was developed which allows the programmer to specify what parts of the program should be deliberated over (to find a plan). The program can perform some planning, then execute the plan and acquire new information, then do more planning, etc. The execution of a plan generated by a search block is automatically monitored and replanning is done when failures or changing conditions require it. We are currently extending the interpreter to support the generation of plans which themselves contain sensing actions. IndiGolog also supports a simple form of contingent planning where the dynamic environment is modeled as a simple deterministic reactive program. This is also being extended to deal with more complex nondeterministic environments. In parallel with this, extensions to the framework to deal with stochastic actions, uncertain knowledge, noisy sensors, temporal constraints, continuous processes, etc. are under development. Tools have also been developed to verify programs written in the framework.

Cognitive Robotics Group members.

Many robotics applications have been developed using our framework. At York University, a mail delivery robot application was implemented which optimized delivery routes and replanned routes when failures occurred or new orders arrived. At the University of Toronto a coffee delivery robot application that optimized temporal constraints was implemented. The framework was adapted for use in programming very inexpensive Lego Mindstorm^® robots. Golog was also used as part of a very successful museum guide robot application developed at the University of Bonn in Germany, and later demonstrated at the Smithsonian in Washington. Our approach has influenced work at NASA on autonomous agents for spacecraft control. We have also been collaborating with MD Robotics (designers of the robot arms of the space shuttle and space station) on space vision applications.

Our framework has also been used to develop software agent applications, such as a banking assistant. An extension of Golog is currently being used at Stanford University for web service customization and composition.

Links:
http://www.cs.toronto.edu/cogrobo/
http://www.cs.yorku.ca/~lesperan/

Please contact:
Yves Lespérance, York University, Toronto, Canada
E-mail: lesperan@cs.yorku.ca

Hector J. Levesque, University of Toronto, Canada
E-mail: hector@cs.toronto.edu