The next day you try an experiment. After giving all your drivers cell phones, PDAs, and GPS navigation systems, you tell them to communicate with each other and the customers to create their own schedule. You also make the drivers responsible for negotiating solutions to any troubles encountered en route. In effect, you have rendered your job as a central dispatcher obsolete, leaving more time for other office management tasks. But will the drivers, operating without central knowledge, find the most cost effective route? Which solution will fulfill (or exceed) company goals and objectives?

These questions are at the heart of the debate between traditional optimization techniques and agent-based modeling (ABM) (also referred to as multi-agent systems [MAS]) [1]. ABM has been lurking on the fringes of the operations research field for some time now. The April 1996 issue of OR/MS Today, for example, touts agents as a solution in call center management for Promus Hotel Corporation [2]. Fast forward to February 2005 and ABM is seen emerging as a powerful simulation tool, with roots in the fields of artificial intelligence, social network theory and cognitive science that has grown to encompass techniques in operations research [3]. Most recently in August of 2006, agents appear as a serious and useful simulation technique for a variety of fields [4]. While this depiction throughout the years has exposed the dominating trends in agent research, it has failed to highlight the similarities and differences, strengths and weaknesses of traditional optimization and agent based techniques.

We recently explored the qualitative boundary between O.R. and ABM, in a series of 20 interviews conducted with personnel spanning two continents (North America and Europe) as well as industry and academia. (For a quantitative comparison of a MAS and optimization approach, see, e.g. [5]). The 10 respondents from academia held expertise in artificial intelligence, operations research, computer science, economics and management science. The respondents from industry encompassed problem holders, software developers and solution providers. Through these interviews, we came to the conclusion that the gap between O.R. and ABM is neither as large nor as unbridgeable as the prevailing stereotypes of O.R. and ABM research may indicate.

Similarities and Differences


The similarities between agents and optimization techniques lay primarily in their goal. The goal of both techniques is to model problems and then advise on decision-making. Furthermore, agents and optimization techniques have uses in the same domains. Just as optimization has its origins in World War II, agents are currently used quite extensively in the defense industry. Dr. V. S. Subrahmanian, a professor in the Department of Computer Science and Director of the Institute for Advanced Computer Studies at the University of Maryland, says that "the success of MAS in the defense field can be measured by increased inquiries and funding from the Department of Defense to academic research groups who develop certain solutions: MAS seems to be quite successful because inquiries and funding are continuing to grow extensively." To further understand the role that both systems can play in one domain, it is necessary to study their differences and subsequently the advantages and disadvantages that these differences bring.

The primary difference between agents and traditional optimization techniques is the level of control — centralized or decentralized. Centralization, as exploited in optimization techniques, can be physically embodied as a person at the center of operations (as was the dispatcher in the opening paragraphs) or virtually present due to high-levels of data aggregation in a central database. Similarly, decentralization, the context in which agents thrive, can also be physical (as in drivers making decisions in the field) or virtual in terms of multiple software components operating autonomously on the same server.

Irrespective of how the level of control is represented, the implications are the same. As one interviewee, Dennis Huisman (Dutch Railways, Edelman award recipient, 2008) put it: "In O.R. methods, everything is connected to everything." A research consultant, Jan Peter Larssen of Almende (a Dutch research company focused on applying multi-agent technology), phrased this same concept as "O.R. methods cannot handle locality." Alternately, Tamás Máhr, a researcher also working with Almende, noted that, "basically agents can be used to represent interests. They can be installed at a variety of sites along a supply chain or within a business network."

Given this fundamental difference in the two techniques, what advantages and disadvantages can we extract from the two systems to further the field of informed decision-making?

Advantages and Disadvantages


Centralization and the mathematically rigorous techniques of optimization can yield benefits other than just an optimal solution. As Rob Zuidwijk, an associate professor at the Rotterdam School of Management, Erasmus University, noted, looking at a problem in a holistic fashion (as required by optimization techniques) "increases the understanding of the problem...because it requires that the question be well-defined." In a similar vein, Roel van de Vrande, a sales manager at Quyntess, emphasizes that "O.R. systems can be used to offer transparency in decisions." This deep understanding of the problem or transparency of decisions made is not always present in agent-based approaches.

Kafui Monu, a Ph.D. candidate at the University of British Columbia, remarked that "in many cases, computer scientists often lack a framework; they just start programming right away. In contrast, business people and business students, with an economic background, prefer to develop a comprehensive framework that includes all surrounding factors, instead of only looking at the programming code."

The idea that a centralized optimization-based solution to a problem is the optimal solution can, however, be a disadvantage. Pedro Szekely, an assistant professor at the University of Southern California, emphasized that "defining these models is a challenge, and it is always imprecise, or estimates can simply be wrong. Then you end up employing sophisticated algorithms with the wrong numbers." The need for well-calibrated input can be a significant challenge in complex environments. As Bastiaan van de Rakt, a joint owner of INITI8, remarked, "O.R. methods fail in very complex and dynamic (inter) organization structures and are difficult to use for detail-level analysis since the focus is on high level parameters. It doesn't explain events on a small scale." This same concept was eloquently stated by Joost van Dijk of DEAL Services when he said, "O.R. tends to freeze reality."

Aside from the challenges of complexity or dynamism, optimization techniques are often described as unnatural or inappropriate in their handling of the "real-world." This was captured by Jan Peter Larssen of Almende when he said that, "by using O.R. methods, many constraints that are soft in nature, are modeled as being hard constraints, or cannot be modeled at all. This means centralized methods are not really able to work with the real problem. Furthermore, humans cannot work well in cooperation with schedules that are made with O.R. methods, because humans like to take different factors into account as well. For instance: goodwill. Often this is not possible to handle in an O.R. method and therefore a user might not accept the decision of O.R. methods."

To some extent the advantages of a distributed agent system can overcome the disadvantages of optimization-based techniques. A PhD Candidate at the Rotterdam School of Management Erasmus University, Hans Moonen, summarized the advantages of MAS as follows: "There are two main advantages of MAS. The first is its ability to handle dynamism: MAS is able to handle situations where information becomes available at a very late timing. For instance, a sudden change of the entire plan. The second advantage is the MAS offer the ability of negotiating between different stakeholders."

John Collins, a professor in the department of Computer Science at the University of Minnesota, highlighted the first advantage when describing the short decision time of MAS — "Agent systems can be very reactive to new events, whereas O.R. methods may need too much time to recalculate an entire solution when a sudden change occurs."

The second advantage of negotiation is not necessarily unique to agents. What, however, is unique is the way in which agents can negotiate a global solution based on local beliefs using distinctly human tactics. For example, Bastiaan van de Rakt emphasized information hiding as a critical business success factor for MAS — "not all parties in a supply chain are willing to share critical decision information with each other. MAS can support quick decision-making by negotiating a feasible solution to the problem on hand without revealing critical internal information at any moment in time. With a high number of parties involved it is still possible to achieve a solution." These two advantages have led researchers to view agents as a natural metaphor to many real-world dynamic scenarios such as supply-chain management and transportation. This is emphasized by the comments of Peter-Paul van Maanen, a research scientist at TNO. Van Maanen said that "MAS provide a good cognitive model of human societies, and humans can easily understand the role based representation of agents."

The advantages of agents do not, however, come without any disadvantages. The biggest disadvantage in MAS is the lack of an optimal solution. As Dennis Huisman put it: "MAS technology usually does not deliver an optimal solution. In fact, when working with MAS you are never sure how optimal its solutions are." This lack of an optimal seems to stem from the uncertainty that pervades MAS. As pointed out by John Collins, "You cannot precisely control what is happening in a MAS, because agents make their own choices at run time. Besides, emergent behavior may occur that is unexpected for the business in which the MAS is operating, which could cause troubles."

It appears that this lack of control has hindered the adoption of MAS in industry as noted by our interviewees. MAS has been used successfully in academia for many years now, but in industry it is still not widely used. Luc Scheidel, a principal consultant at Capgemini, reasons that, "It is not proven technology that can be bought off-the-shelf. When you want to use it, companies have to do some more work by themselves. They need the knowledge in order to do that, and experience." This perception was echoed by Haizhen Zhang, a researcher at Microsoft, when he said, "It is hard to actually build a MAS framework; creating the foundations is difficult. Many of those frameworks are developed by different researchers. But it is hard to generalize those formal frameworks into different scenarios for useful applications."

A Hybrid Solution


So, which approach will meet a company's objectives better? Probably neither. Both systems working in concert have far more potential to solve large-scale business problems than either system working alone. The value of such a hybrid solution can be seen most clearly when dissecting a problem along the three temporal lines of operational, tactical and strategic planning.

As Walther Ploos van Amstel, a member of the board of directors at Versteijnen Logistics, explained: "For tactical applications, it is advised to use O.R. methods. Run O.R. simulations, and then develop 'rules of thumb' for tactical decisions. Considering strategic decisions, such as deciding on which customers a company should focus on, or where a distribution center should be located, O.R. methods are better, too. In both cases this is because of the optimal solutions that it presents. However, for operational decisions, a combination of O.R. and MAS should be employed. O.R. should be used to calculate the preliminary plan, such as the amount of cargo, schedules, etc., using the plan-do-act methodology. After this, MAS can be used for fine-tuning those plans, because of occurring unexpected events. It is impossible to recalculate the entire solution using O.R. methods, and therefore MAS techniques should be used to make dynamic alterations to the plan."

The notion of a hybrid solution is not only an exercise in speculation. For example, The Trading Agent Competition (TAC) [http://tradingagents.org/], an international forum hosting competitions since 2000 to promote and encourage research on trading agents, has seen the emergence of agents that incorporate many optimization-based techniques to help solve their challenging real-time bidding and procurement tasks. In fact, the most successful trading agents adopt and extend state-of-the-art techniques from artificial intelligence, operations research, statistics, and a variety of relevant fields [6]. The hybrid solution was also favored by many of our survey participants, such as by Willem-Jan van Hoeve, assistant professor of Operations Research at the Tepper School of Business of Carnegie Mellon University: "Where O.R. depends on some form of matrix algebra, MAS is able to handle many different forms of mathematical expressions," he says. "But a hybrid approach that combines O.R. and MAS could also be a good solution."

The emergence of an optimization/MAS hybrid solution in the TAC community and among our interviewees should serve as a harbinger to researchers. The future for both O.R. and MAS lies in the ability of the two methodologies to communicate with each other. There is a need for a more natural and smoother integration of both techniques. How can the handoff from an optimal solution to a MAS implementation be orchestrated? How will the MAS execution affect the optimality of the optimization-based solution? How can the emergent behavior of the MAS be monitored and fed back into the optimization? These are the questions that await a new generation of interdisciplinary researchers.



Wolfgang Ketter (WKetter@rsm.nlis) is an assistant professor at the Department of Decision and Information Sciences at the Rotterdam School of Management of the Erasmus University. He founded and runs the Learning Agents Research Group at Erasmus (LARGE).

F. Jordan Srour (JSrour@rsm.nl) is a third-year Ph.D. candidate at the Rotterdam School of Management, Erasmus University. Prior to pursuing her Ph.D., she worked as a transportation engineer evaluating new freight technologies at Science Applications International Corporation.

Acknowledgment The authors would like to thank all of the researchers for sharing their time and insights with us. We also thank Bas van Dijke, a master's student at the Rotterdam School of Management, Erasmus University, for conducting these interviews as part of his thesis requirement.

1. M. Wooldridge and N. Jennings, 1995, "Intelligent agents: theory and practice," Knowledge Engineering Review, Vol. 10, No. 2, pp. 115 — 152.
2. D. Blanchard, 1996, "Cutting Edge: Promus Hotel Implements Intelligent Agents," OR/MS Today, Vol. 23, No. 2, April 1996.
3. D. Samuelson, 2005, "Agents of Change: How agent-based modeling may transform social science," OR/MS Today, Vol. 32, No. 1, February 2005.
4. D. Samuelson and M. Charles, 2006, "Agent-Based Simulation Comes of Age: Software opens up many new areas of application," OR/MS Today, Vol. 33, No. 4, August 2006.
5. T. Máhr, J. Srour, M. deWeerdt and R. Zuidwijk, 2008, "Agent performance in vehicle routing when the only thing certain is uncertainty," Proceedings of Agents in Traffic and Transportation Workshop at 7th International Conference on Autonomous Agents and Multiagent Systems, May 2008, Estoril, Portugal.
6. W. Ketter, J. Collins, M. Gini, A. Gupta, P. Schrater, 2007, "Pricing and Resource Allocation for Intelligent Trading Agents using Economic Regimes," Proceedings of 9th International Conference on Electronic Commerce, Minneapolis, August 2007.

Table of Contents

OR/MS Today Home Page


OR/MS Today copyright © 2009 by the Institute for Operations Research and the Management Sciences. All rights reserved.


Lionheart Publishing, Inc.
506 Roswell Rd., Suite 220, Marietta, GA 30060 USA
Phone: 770-431-0867 | Fax: 770-432-6969
E-mail: lpi@lionhrtpub.com
URL: http://www.lionhrtpub.com


Web Site © Copyright 2009 by Lionheart Publishing, Inc. All rights reserved.