Gini and Students Feel the MAGNETic Pull of E-Commerce
Picture, left to right: Row 1: Espen Sigvarsten, Guleser Dmir, Yelena,
Schoolcraft, Maria Gini, Ashutosh Jaswal; Row 2:
Stefan Botman, Mark Hoogendoorn,
Wolfgang Ketter, Alex Babanov, John Collins.
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