One of my favorite mottos is, If you want a job done right, do it yourself! It's generally sage advice, but unfortunately even the best of us are limited by what we can accomplish ourselves. What we really need is a helpful assistant, a tireless gopher, someone -- or something -- to take care of the tedious administrative details of everyday life: finding the lowest priced product, waiting in line for those hard-to-get concert tickets, doing our taxes. In short, we all need an agent.
If this sounds familiar, it may be because you and I have read the same whitepapers, press releases, and shallow articles. They're filled with all sorts of good ideas about what agents should do, but they neglect to come clean with what agents can do.
You see, in order to actually do some of the things their promoters promise, agents have to be given the ability to think. And people have been trying -- with little success -- to get computers to think since the '60s.
Artificial Intelligence means never having to say you're sorry
The one point missed by many intelligent-agent aficionados (especially those promoting commercial products) is that artificial intelligence (AI) is hard to come by. Over thirty years have passed since Slagle penned his now-famous Artificial Intelligence: The Heuristic Approach. LISP, the longtime darling of the AI community, was developed at MIT back in the '50s, well before many of us were even born. And now, as the millennium slowly approaches, we find we still haven't built our HAL 9000.
As a result, many dreams of intelligent agents have turned to dust. And the failed hype has put a bit of tarnish on agents and agent technology. Despite all this, I believe there are at least two valid reasons to give your agents a touch of the smarts (especially if they're of the mobile variety):
Mobile agents must operate reliably even when they're not in contact with you or their home base. Remember, mobile agents may live in environments with poor network reliability.
Many of the problems agents need to solve are not well suited to strictly procedural solutions. Agents may need to move from host to host, asking questions and accumulating information; they need the capacity to deal with a vague final destination while calculating their immediate destination, at each step of the way, based on analysis of the information they've acquired.
Artificial Intelligence, neural networks, expert systems -- oh my!
There are many tools and techniques for making machines think; AI is a broad field of endeavor. At one end are neural networks -- computing systems designed to mimic the low-level structure and function of the nervous system. At the other end are expert systems -- computing systems designed to imitate higher level cognitive processing.
Because higher level cognitive processing is what we're shooting for, let's take a closer look at expert systems.
Expert systems and agents
An expert system performs a set of activities traditionally associated with highly skilled or knowledgeable humans -- activities like medical diagnosis and stock market analysis. Admittedly, we don't want our agents to be skilled in these fields, however we do want them to be competent entities in the environments in which they live.
A rule-based expert system is an expert system that uses a set of rules as its knowledge base. Rules are simple (and not-so-simple) statements of the form: If some condition is true, then do something.
Rule-based expert systems combine well with agents for two reasons:
Rules make a compact definition of behavior possible. In its simplest form, a behavior is a set of actions and the conditions under which those actions should happen.
From a purely visual perspective, once you get the hang of the notation for rules, it's much easier to understand system activity by examining a set of rules than by unwinding the equivalent nested
I suspect some of you may be skeptical. After all, conventional procedural languages like C, C++, Java, and Smalltalk (along with many others) have made possible the construction of some truly remarkable applications and have allowed programmers to solve many important real-world problems. While this is true, it doesn't always follow that procedural languages are the right tool for the job at hand.
Consider for a moment, from a purely conceptual standpoint, what autonomous mobile agents must do. Most are created and given a task to perform, often in the absence of communication with their creator. The task an agent is given might be simple -- easily described with a linear series of steps -- or it might be complex -- consisting of actions that take place only under certain conditions. For example, an agent's task may consist of actions that take form based on preceding actions.
Using a procedural programming language, you must not only tell the agent what to do, you must also tell it exactly how to do it. For a complex task, the control logic quickly becomes difficult to write, debug, and maintain.
What's ironic is the fact that when we build applications, we typically develop or determine the rules first. Then, when we feel we understand the desired behavior, we turn around and try to code the rules in a procedural programming language. A rule-based expert system allows us to avoid, to some degree, the last step. In my opinion, that's one less point of entry for bugs.
Consider the issue from another angle. Behavior is the basis of autonomy. And rules are a concise definition of behavior. And expert systems are very good and very efficient at applying rules. You could do it all by hand, but why bother?
A rule is nothing more than a concise description of a set of conditions and a set of actions to take if the conditions are true.
In English, a rule might look as follows:
If the price of a widget is less than 0, buy the widget.
If this merchant doesn't sell widgets, go to the next merchant on the itinerary.
It's all too easy to translate examples such as these into statements in a procedural programming language. Thus, the benefits of rules aren't immediately clear.
if (widget.price < 50.0)
Nevertheless, let's take a look at how we might write each of these rules in a fictitious expert system language (I'll show you the real language shortly).
condition: widget.price < 50.0
condition: ! merchant.sells("widget")
A rule-based expert system continually tests a set of conditional statements (known as rules) against a database of data (known as facts) to see if any apply. If a rule applies, the expert system executes the associated actions.
Jess -- the Java expert system shell
The code that makes an expert system work is very interesting in its own right. It's also too large in scope for this column. Fortunately, several decent expert systems are already written and widely available -- some are even written in Java.
I selected Jess, the Java expert system shell, as my engine. Jess was written entirely in Java by Ernest Friedman-Hill at Sandia National Laboratories. It's fast, compact, and easily integrated into other systems. It's also being actively improved, both in performance and functionality, and the source code is readily available (see Resources).
Jess is a clone of the CLIPS expert system shell (a shell is the expert system minus any rules). Jess (and CLIPS) provide their own notation for defining rules. The syntax of the Jess language is reminiscent of LISP. Because of that (or perhaps in spite of that) the language is very easy to read.
Facts and rules
As I mentioned earlier, two important constructs make up a rule-based expert system's knowledge base: facts and rules.
A fact is a construct that defines a piece of information that is known to be true: the sun is hot, the sky is blue, the merchant sells radios (you get the idea).
A rule is nothing more than an
if/then statement that defines the set of facts that must be true (the if part) before a set of actions (the then part) can be executed.
Rule-based expert systems are extremely powerful because actions themselves can assert new facts. When this happens additional rules apply and their actions are executed.
A fact in Jess is written as follows:
(bear "papa" big hungry angry)
(bear "mama" small hungry grumpy)
The first fact states that the
price (of something) is 0. The second two facts state that there is a
"papa", who is
angry, and another
"mama", who is
Rules look like this:
(bear "papa" big hungry happy)
(feed-the-bear "papa" "honey")
defrule keyword indicates that the statement is a rule definition. Every rule has a name -- in this case the name of the rule is
feed-bear. The next two lines contain conditions (or facts) that must be true before this rule will be activated. The first fact specifies that the system's
mood must be
friendly, and the second specifies that there must be a
"papa". When both of these conditions are true, the expert system will
Unfortunately, given what we know about the bears named
"mama", no bear will be fed today.
The rule above is very specific. It applies to only one
bear. The rule below is much more general:
(bear ?name ?size hungry ?mood)
This rule contains three variables. Variables begin with a question mark (?). When present in conditions, they match anything. The condition in the second line of the rule above will match any
bear as long as it is
The agent hooks
As I mentioned before, Jess is easily integrated with other systems, including the agent system we've been building. In order to customize Jess for our system, we need to add commands for sending messages and transferring agents. Rules can then utilize these commands in their action lists.
The command that sends a message to another agent looks like this:
(send <agent> "<message name>" <parameter> <parameter> ...)
The following example shows how to send the Start message to the agent with the name "counter":
(send "counter" "Start")
The command that transfers an agent looks like this:
(transfer "<agent host name>")
The following example demonstrates how an agent would initiate a transfer to the host named "rmi://frodo/ki":
JessAgentFunctions implements both of these commands.
The source code provided implements a few other useful commands, such as
list, which returns all published agents;
hostname, which returns the hostname of the agent host; and
self, which returns the identity of the agent.
Armed with these commands, you can quickly write rules that will give your agents new dimensions of autonomy.
Our example: the broker
A broker is essentially a middleman. It executes trades on the behalf other parties -- in our case, buyers and sellers. Buyer agents and seller agents contact our broker agent and express a desire to buy or sell a product. The broker matches buyers and sellers and executes the trade.
Here are the rules that define this behavior:
(requires ?buyer ?product1) ; the buyer requires product1
(provides ?seller ?product2) ; the seller provides product2
(test (eq ?product1 ?product2)) ; product1 and product2 are the same
(send ?seller "Order" ?product2) ; order from the seller
(send ?buyer "Delivery" ?product1) ; deliver to the buyer
;; The construct [variable <- condition] in the two rules below does
;; nothing more than match the specified condition to a fact and put
;; the fact identity in the variable ?rule. This allows us to retract
;; the fact. Retracting the fact prevents the agent from repeatedly
;; matching these two rules for the same buyer and seller.
?fact <- (new-buyer ?buyer) ; if there is a new a buyer...
(foreach ?i (nth$ 2 (send ?buyer "GetProducts"))
(assert (requires ?buyer ?i)) ; get the products the buyer requires
; and for each one create a fact
; associating the buyer and the product
?fact <- (new-seller ?seller) ; if there is a new seller...
(foreach ?i (nth$ 2 (send ?seller "GetProducts"))
(assert (provides ?seller ?i)) ; get the products the seller provides
; and for each one create a fact
; associating the seller and the product
The point to remember is that we've merely defined what we want. The expert system takes care of making it happen.
JessAgent is the complete Java source code for a Jess-aware agent.
Admittedly, I could have just as easily written the example above using a conventional procedural programming language with no appreciable loss of functionality. However, as systems grow and the environments in which they live become more complex, the development task becomes harder and harder, and the procedural solution becomes increasingly difficult to get right. Rule-based expert systems allow agents to solve these problems flexibly and reliably -- two very important requirements for a piece of software operating beyond direct supervision.
Learn more about this topic
- Download the source code http://www.etcee.com/javaworld/ki/index.html
- Read up on Jess, the Java expert system shell http://herzberg.ca.sandia.gov/jess
- The CLIPS expert system shell http://www.ghg.net/clips/CLIPS.html
- See all of Todd's previous How-To Java columns http://www.javaworld.com/topicalindex/jw-ti-howto.html