You stand at your back door and think, "That old garage isn't going to hold up under many more Minnesota thunderstorms. I'd be better off tearing it down and building a new one." You don't have a lot of money, so you decide to be your own general contractor. There is a lot of work ahead. You will look up electricians, masons, roofers, and garage door companies. You will make a lot of calls and try to get estimates of what can be done when and for how much. Then you have to figure out which companies to choose so that the project runs smoothly and under budget. Paying a general contractor is starting to look pretty good!
A few years later, you are once again looking at your garage. It never was rebuilt because doing so was just too much hassle. It has survived so far, but it's definitely on its last legs. As you gaze at the garage wondering what to do, your attention is caught by a story on the TV about a new online marketplace called MAGNET. You decide to check it out. MAGNET assigns you your very own software agent, which helps create a plan for the job you want done. You list all the tasks, the order to do them in, and the general time frame in which it all needs to happen. Then your agent sends your request to the market. Within a few hours, you have received many bids from the agents of contractors in your area. Your MAGNET agent sorts through the bids and helps you see which ones will work together in a good schedule for the best price. You make your choices and send out awards. The first workers will be showing up tomorrow!
While the actual MAGNET (MultiAGent NEgotiation Testbed) system is not yet ready for the scenario above, it is heading that way. Maria Gini and her team of thirteen students have been working to make this e-commerce dream a reality.
Agents in MAGNET are intended to negotiate and monitor the execution of contracts among multiple suppliers. Each agent is an independent entity, with its own structure, goals, and resources. In general, the resources under "control" of an individual agent are not sufficient to satisfy that agent's goals, and so the agent must negotiate with other agents in order to meet its goals.
We distinguish between two agent roles, the Customer and the Supplier. A Customer is an agent who needs resources outside of its direct control in order to carry out its plans. In response to a Request for Quotes, some Supplier agents may offer to provide the requested resources or services, for specified prices, over specified time periods. This is carried out as a first-price sealed-bid combinatorial auction. Once the Customer agent receives bids, it evaluates them and selects the optimal set of bids which satisfy its goals. Suppliers are then notified of their commitments, and the Execution Manager is called to oversee completion of the plan. Plan maintenance includes re-negotiating existing commitments, re-bidding portions of the plan, replanning, and abandoning the goal.
The Customer agents are already well-developed. They are equipped with a variety of search algorithms they use when they evaluate bids. The agents can use simulated annealing, integer programming, A* search or iterative deepening A* search to work their way through the myriad of bid combinations. The Customer agent's objective is to maximize utility, which requires minimizing cost and risk of not accomplishing the goal. To determine which bids to accept, the Customer agent considers coverage (we assume that there is no point in accomplishing only a part of the goal), temporal feasibility (the time windows for tasks must allow to compose them in a feasible schedule), cost, and risk. Risk factors include elements such as availability of suppliers, supplier reliability, profit margin, expected cost of recovering from supplier decommitment or delay, loss of value if the end date is delayed, cost of plan failure.
The Customer agent and supporting infrastructure is being released as open source at http://sourceforge.net/projects/magnet/. The software is completely written in Java, and has been tested on multiple platforms. Ongoing research includes applying the economic theory of Expected Utility to the generation of requests for quotes, completion of the design and implementation of supplier agents, and design of an evolutionary simulation environment developed to study relative performance of agents.
You sit with your cup of coffee looking out the window at the workers finishing your new garage. You smile as you realize it has been built cheaper and faster than you expected, and you hardly had to do any legwork. The ease with which it all came together was mesmerizing. "This would be a huge help at work!" you think. But maybe you should wait until there's been some more rigorous testing. Maybe it's time to build that pool you've always wanted...
Additional information at http://www.cs.umn.edu/magnet.
Partial support for this research was provided by NSF under award NSF/IIS-0084202 and by a UROP grant to Vasile Bud.
-Anne Schoolcraft and Maria Gini