Computer Science and Engineering
Storey Innovation Center
550 Assembly Street, RM 2200
Columbia, SC 29201
Multiagent systems, agent-based modeling, web applications, algorithmic game theory, negotiation networks, distributed algorithms.
Ann Arbor, MI
PhD. Computer Science and Engineering
Thesis: Computational Agents that Learn About Agents:
Algorithms for Their Design and a Predictive Theory of Their
PhD. Committee: Edmund H. Durfee, Robert Axelrod, William P. Birmingham, John H. Laird, Mike Wellman.
M.S. Computer Science
Research in automatic proofs of parallel programs.
B.S. Computer Science and Engineering
Ann Arbor, MI
Member of the University of Michigan Digital Library project. Developed software agents using the University of Michigan Procedural Reasoning System, C++, and CORBA.
Member of Technical Staff
Responsible for significant part of code that controls phone companies' service order handling system. Developed set of database access routines.
Designed and developed interface for multimedia user help system. The interface consists of device drivers for communications between PCs, Point of Sale terminal, expert system and laser-disc. Code was written in 386 assembly and C.
Researched the viability of using neural networks for the prediction of sales volume in a commercial establishment, using environmental conditions as input. Serviced and helped install several local area networks.
Rio Piedras, PR
Taught seminars on basic computer skills to different audiences ranging from high school students to university professors. Designed and taught a seminar on Artificial Intelligence.
Worked in the testing and debugging of the Actor model of computation as implemented in the Symbolics Lisp machine. Served as member of the Message Passing Semantics group at CSAIL.
Programmer and System Administrator
Developed several programs for mathematical analysis and estimation of commodity trends in the stock market. Helped with maintenance and use of IBM personal computers.
Developed editor for InaJo language using Emacs-Lisp. Designed several tools for debugging InaJo programs. Participated in development of secure operating system.
Google Scholar Profile
Abstract: Traffic accidents occur every day, causing disruptions. The longer disruptions are in place, the more severe they may become as additional vehicles continue to enter the affected roadways. This paper looks at using passive data from a readily available source, smart phones, to detect traffic accidents automatically via machine learning algorithms and thereby allow additional alerts and actions to occur to minimize the disruption. Using simulated data, machine learning algorithms were scored for accuracy and the results were analyzed.
Abstract: This paper presents findings of an observational study of the Registered Nurse (RN) Medication Administration Process (MAP) conducted on two comparable medical units in a large urban tertiary care medical center in Columbia, South Carolina. A total of 305 individual MAP observations were recorded over a 6-week period with an average of 5 MAP observations per RN participant for both clinical units. A key MAP variation was identified in terms of unbundled versus bundled MAP performance. In the unbundled workflow, an RN engages in the MAP by performing only MAP tasks during a care episode. In the bundled workflow, an RN completes medication administration along with other patient care responsibilities during the care episode. Using a discrete-event simulation model, this paper addresses the difference between unbundled and bundled workflow and their effects on simulated redesign interventions.
Abstract: This study examined the use of voice recognition technology in perioperative services (Periop) to enable Periop staff to record workflow milestones using mobile technology. The use of mobile technology to improve patient flow and quality of care could be facilitated if such voice recognition technology could be made robust. The goal of this experiment was to allow the Periop staff to provide care without being interrupted with data entry and querying tasks. However, the results are generalizable to other situations where an engineering manager attempts to improve communication performance using mobile technology. This study enhanced Google's voice recognition capability by using post-processing classifiers (i.e., bag-of-sentences, support vector machine, and maximum entropy). The experiments investigated three factors (original phrasing, reduced phrasing, and personalized phrasing) at three levels (zero training repetition, 5 training repetitions, and 10 training repetitions). Results indicated that personal phrasing yielded the highest correctness and that training the device to recognize an individual's voice improved correctness as well. Although simplistic, the bag-of-sentences classifier significantly improved voice recognition correctness. The classification efficiency of the maximum entropy and support vector machine algorithms was found to be nearly identical. These results suggest that engineering managers could significantly enhance Google's voice recognition technology by using post-processing techniques, which would facilitate its use in health care and other applications.
Abstract: Direct observation of complex health-care processes typically involves multi-observer recording of sequential process tasks. Inference, the key validity threat to multi-observer recording, is controlled with observer training and assessment for the degree of recording consistency across observers. The gold standard for assessing recording consistency is the Kappa statistic, which assumes an exact task sequence match among observers. This assumption, however, is often difficult to meet with health-care process observations where task speed and complexity can result in uneven task sequence recording among observers. The edit distance approach, derived from information string theory, is not predicated on an exact task sequence match and offers an alternative to the Kappa statistic for assessing multi-observer agreement. The paper uses simultaneously recorded process observations with uneven task sequences made by three observers to compare agreement results for the edit distance approach and Kappa statistic. Edit distance approach strengths and limitations are discussed.
Abstract: Agent-based modeling is used to simulate human behaviors in different fields. The process of building believable models of human behavior requires that domain experts and Artificial Intelligence experts work closely together to build custom models for each domain, which requires significant effort. The aim of this study is to automate at least some parts of this process. We present an algorithm called magic, which produces an agent behavioral model from raw observational data. It calculates transition probabilities between actions and identifies decision points at which the agent requires additional information in order to choose the appropriate action. Our experiments using synthetically-generated data and real-world data from a hospital setting show that the magic algorithm can automatically produce an agent decision process. The agent's underlying behavior can then be modified by domain experts, thus reducing the complexity of producing believable agent behavior from field data.
Abstract: Coordinated group motion has been studied extensively both in real systems (flocks, swarms and schools) and in simulations (self-propelled particle (SPP) models using attraction and repulsion rules). Rarely are attraction and repulsion rules manipulated, and the resulting emergent behaviours of real and simulation systems are compared. We compare swarms of sensory- eprived whirligig beetles with matching simulation models. Whirligigs live at the water's surface and coordinate their grouping using their eyes and antennae. We filmed groups of beetles in which antennae or eyes had been unilaterally obstructed and measured individual and group behaviours. We then developed and compared eight SPP simulation models. Eye-less beetles formed larger diameter resting groups than antenna-less or control groups. Antenna-less groups collided more often with each other during evasive group movements than did eye-less or control groups. Simulations of antenna-less individuals produced no difference from a control (or a slight decrease) in group diameter. Simulations of eye-less individuals produced an increase in group diameter. Our study is important in (i) differentiating between group attraction and repulsion rules, (ii) directly comparing emergent properties of real and simulated groups, and (iii) exploring a new sensory modality (surface wave detection) to coordinate group movement.
Abstract: This NSF-funded study examines how the use of mobile technology affects patient flow and quality of care in perioperative services. The researchers interviewed hospital managers and staff to determine their expectations about incorporating technology into their workflow. Both support development of reliable voice recognition capability to enable hands-free patient care.
Abstract: Distributed Constraint programming (DisCSP/DisCOP) is a programming approach used to describe and solve large classes of problems such as searching, combinatorial and planning problems. This type of distributed modelling appeared naturally for many problems for which the information was distributed to many agents. Modelling and simulation are essential tools in many areas of science and engineering, including computer science. The purpose of this article is to present an open-source solution for implementation and evaluation of the distributed constraints in NetLogo, model that can be run on a cluster of computers. Such a tool allows using various search techniques also the evaluation and analysis of performances of the asynchronous searching techniques. Also, in this paper we have developed a methodology to run the NetLogo models in a cluster computing environment or on a single machine, varying both parameter values and/or the random number of agents.
Abstract: Simulation models regarding groups of fish and birds based on individual movement decision rules have become increasingly sophisticated. Recent studies have started to tie together how the rules of homogeneous independent-acting individuals lead to emergent group behaviors. However, there is less research on the role that heterogeneity within a group has on these emergent properties. Heterogeneity in real animal groups due to hunger, sex, body size, species, and age can influence speed, nearest neighbor distance, and viewing angle. In our study we examine how differences in viewing angle (or its complement: blind zone) within a group influence emergent properties such as group size, polarization, group shape, and segregation. Simulated groups were assembled with different mixes of blind zones (e.g. half the members with a blind zone of 60 degrees and half with a blind zone of 120 degrees). Significant differences in many of the measured emergent properties were found and were related to the level of heterogeneity as well as the absolute value of the blind zone. In homogeneous groups, increased values for the blind zone led to groups that were: smaller, more elongated, and denser. In heterogeneous groups the sum of blind zones predicted emergent group behaviors. Specifically, as the sum of the blind zones increased: group size and density decreased and the shape of the group became rounder. However, several mixes produced emergent properties that were very different than the predicted regressions. Our findings suggest that it will be important for researchers to look at how individual differences in blind zones within real groups such as fish schools and bird flocks influence emergent behaviors. Our findings also have applications to designing sensor systems for car navigation systems and robotic arrays.
Abstract: Due to the importance of drayage operations, operators at marine container terminals are increasingly looking to reduce the time a truck spends at the terminal to complete a transaction. This study introduces an agent-based approach to model yard cranes for the analysis of truck turn time. The objective of the model is to solve the yard crane scheduling problem (i.e. determining the sequence of drayage trucks to serve to minimize their waiting time). It is accomplished by modeling the yard crane operators as agents that employ reinforcement learning; specifically, q-learning. The proposed agent-based, q-learning model is developed using Netlogo. Experimental results show that the q-learning model is very effective in assisting the yard crane operator to select the next best move. Thus, the proposed q-learning model could potentially be integrated into existing yard management systems to automate the truck selection process and thereby improve yard operations.
Abstract: The medication administration process (MAP) is one of the most high-risk processes in health care. MAP workflow redesign can precipitate both unanticipated and unintended consequences that can lead to new medication safety risks and workflow inefficiencies. Thus, it is necessary to have a tool to evaluate the impact of redesign approaches in advance of their clinical implementation. This paper discusses the development of an agent-based MAP computer simulation model that can be used to assess the impact of MAP workflow redesign on MAP performance. The agent-based approach is adopted in order to capture Registered Nurse medication administration performance. The process of designing, developing, validating, and testing such a model is explained. Work is underway to collect MAP data in a hospital setting to provide more complex MAP observations to extend development of the model to better represent the complexity of MAP.
Abstract: This paper addresses the need by terminal operators to optimise the yard crane operations at seaport terminals. It introduces a novel agent-based approach to model yard cranes, where each crane acts as an autonomous agent that seeks to maximise its utility. A key component of the proposed agent-based simulation model is a set of utility functions that properly capture the essential decision making attributes of crane operators in choosing the next truck to serve. Simulation results reveal important insights about distance-based service strategy and time-based service strategy and how they can be used together to accomplish the terminal’s operational objectives. The developed simulation tool can be used by terminal management to make strategic planning and/or real-time operational decisions to improve and optimise yard crane operations.
Abstract: The efficiency of yard operations is critical to the overall productivity of a container terminal because the yard serves as the interface between the landside and waterside operations. Most container terminals use yard cranes to transfer containers between the yard and trucks (both external and internal). To facilitate vessel operations, an efficient work schedule for the yard cranes is necessary given varying work volumes among yard blocks with different planning periods. This paper investigated an agent-based approach to assign and relocate yard cranes among yard blocks based on the forecasted work volumes. The goal of our study is to reduce the work volume that remains incomplete at the end of a planning period. We offered several preference functions for yard cranes and blocks which are modeled as agents. These preference functions are designed to find effective schedules for yard cranes. In addition, we examined various rules for the initial assignment of yard cranes to blocks. Our analysis demonstrated that our model can effectively and efficiently reduce the percentage of incomplete work volume for any real-world sized problem
Abstract: Truck queuing at marine terminal gates has long been recognized as a source of emissions problem due to the large number of trucks idling. For this reason, there is a great deal of interest among the different stakeholders to lessen the severity of the problem. An approach being experimented by some terminals to reduce truck queuing at the terminal is to provide live views of their gates via webcams. An assumption made by the terminals in this method is that truck dispatchers and drivers will make rational decisions regarding their departure times such that there will be less fluctuations in truck arrivals at the terminal based on the live information. However, it is clear that if dispatchers send trucks to the terminal whenever the truck queues are short and not send trucks when the truck queues are long, it could lead to a perpetual whip lash effect. This study explores the predictive strategies that need to be made by the various dispatchers to achieve the desired effects (i.e. steady arrival of trucks and hence less queuing at the seaport terminal gates). This problem is studied with the use of an agent-based simulation model and the solution to the well known El Farol Bar problem. Results demonstrate that truck depots can manage (without any collaboration with one another) to minimize congestion at seaport terminal gates by using the provided real-time gate congestion information and some simple logics for estimating the expected truck wait time.
Abstract: Combinatorial auctions (CAs) are a great way to solve complex resource allocation and coordination problems. However, CAs require a central auctioneer who receives the bids and solves the winner determination problem, an NP-hard problem. Unfortunately, a centralized auction is not a good fit for real world situations where the participants have proprietary interests that they wish to remain private or when it is difficult to establish a trusted auctioneer. The work presented here is motivated by the vision of distributed CAs; incentive compatible peer-to-peer mechanisms to solve the allocation problem, where bidders carry out the needed computation. For such a system to exist, both a protocol that distributes the computational task amongst the bidders and strategies for bidding behavior are needed. PAUSE is combinatorial auction mechanism that naturally distributes the computational load amongst the bidders, establishing the protocol or rules the participants must follow. However, it does not provide bidders with bidding strategies. This article revisits and reevaluates a set of bidding algorithms that represent different bidding strategies that bidders can use to engage in a PAUSE auction, presenting a study that analyzes them with respect to the number of goods, bids, and bidders. Results show that PAUSE, along with the aforementioned heuristic bidding algorithms, is a viable method for solving combinatorial allocation problems without a centralized auctioneer.
Abstract: In this study we examine the relationship between supply network’s topology and its robustness in the presence of random failures and targeted attacks. The agent based model developed in this paper uses the basic framework and parameters in the experimental game presented in Sterman (1989) for modeling adaptive managerial decision making in an inventory management context. The study extends the linear supply chain context to a complex supply network and undertakes a rigorous examination of robustness of these supply networks that are characterized by distinct network characteristics. We theorize that network characteristics such as average path length, clustering coefficient, size of the largest connected component in the network and the maximum distance between nodes in the largest connected component are related to the robustness of supply networks, and test the research hypotheses using data from several simulation runs. Simulations were carried out using twenty distinct network topologies where ten of these topologies were generated using preferential attachment approach (based on the theory of scalefree networks) and the remaining ten topologies were generated using random attachment approach (using random graph theory as a foundation). These twenty supply networks were subjected to random demand and their performances were evaluated by considering varying probabilities of random failures of nodes and targeted attacks on nodes. We also consider the severity of these disruptions by considering the downtime of the affected nodes. Using the data collected from a series of simulation experiments, we test the research hypotheses by means of binomial logistic regression analysis. The results point towards a significant association between network characteristics and supply network robustness assessed using multiple performance measures. We discuss the implications of the study and present directions for future research.
Abstract: As commercial supply chains grow into complex global supply networks, more and greater risks are introduced for cooperating and competing companies alike. These networks can be affected by events such as natural disasters, terrorism, and of late, economic downturn. Supply industry leaders, such as IBM, have announced a need for methods to identify and prevent risks in these ever-growing complex networks. Multiagent-based simulation lends itself perfectly to supply network modeling due to its autonomous nature. Our research illustrates a multiagent supply network formation technique using greedy supply agents and limited resource allocation. Using these formations, the resilience of each network is compared with others and assessed so that we may ascertain the characteristics of risky supply network structure. Our results show that an increase in relationship resources results in a more resilient network; however, as the amount of available resources increases, the risk of the most vulnerable agent in the network decreases by a smaller margin.
Abstract: Agent-based models are increasingly being used to simulate and analyze various transportation problems, from traffic flow to air traffic control. One transportation industry that has not received as much attention from the multi-agent systems community is seaport container terminals. It can be argued that the operations that take place at a container terminal are as complex as that of an airport. A seaport container terminal faces a myriad of operational challenges such as optimizing berth space, minimizing ship turnaround time, maximizing use of resources, and reducing wait time of drayage trucks. Due to environmental concerns, terminal operators and port planners are focusing on the problem of reducing the in-terminal wait time of drayage trucks. In this paper, we present our multiagent model of a container yard operation, its implementation using NetLogo, and some initial test results. We model yard cranes as opportunistic utility-maximizing agents using several different utility functions for comparison purposes. By using a representative layout of a terminal our simulation model allows us to analyze the behavior of the cranes and evaluate the collective performance of the system. We demonstrate that it is possible to build a realistic and useful model of yard crane operation. Our test results show that utility functions that give higher precedence to nearby trucks lead to much better results than those that favor serving trucks on a mostly first-come first-serve order.
Abstract: Due to environmental concerns, terminal operators at seaport container terminals are increasingly looking to reduce the time a truck spends at the terminal to complete a transaction. For terminals that stack their containers, the solution may seem obvious: add more yard cranes to reduce trucks’ wait time in the yard. However, the high cost of these cranes often prohibits terminal operators from freely buying more. Another reason is because there is no clear understanding of how the yard cranes’ availability and service strategy affect truck turn time. This study introduces an agent-based approach to model yard cranes for the analysis of truck turn time with respect to service strategy. It is accomplished by modeling the cranes as utility-maximizing agents. This study has identified a set of utility functions that properly capture the essential decision making process of crane operators in choosing the next truck to provide service to. The agent-based model is implemented using NetLogo, a cross-platform multi-agent programmable modeling environment. Simulation results show that the distance-based service strategy produces the best results in terms of average waiting time and the maximum waiting time of any truck.
Abstract: The asynchronous searching techniques are characterized by the fact that each agent instantiates its variables in a concurrent way. Then, it sends the values of its variables to other agents directly connected to it by using messages. These asynchronous techniques have different behaviors in the case of delays in sending messages. This article presents the opportunity for synchronizing the execution of agents in the case of asynchronous techniques. It investigates and compares the behaviors of several asynchronous techniques in two cases: agents process the received messages asynchronously (the real situation) and the synchronous case, when a synchronization of the execution of agents is done, i.e. the agents perform a computing cycle in which they process a message from a message queue. After that, the synchronization is done by waiting for the other agents to finalize the processing of their messages. The experiments show that the synchronization of the agents execution leads to lower costs in searching for solutions. A solution for synchronizing the agents execution is suggested for the analyzed asynchronous techniques.
Abstract: This paper shows how the Asynchronous Backtracking algorithm, a well known distributed constraint satisfaction algorithm, produces unnecessary messages and introduces our optimized algorithm, Message Management Asynchronous Backtracking, which reduces the number of messages the agents send. The message management mechanism removes the redundant messages, keeps message queue updated, and handles messages by package instead of individually in order to improve efficiency. Our test results show the algorithm significantly reduces the total number of messages sent and drastically reduces the number of cycles used when solving instances of the graph coloring problem.
Abstract: Distributed allocation and multiagent coordination problems can be solved through combinatorial auctions (CAs). However, most of the existing winner determination algorithms (WDAs) for CAs are centralized. The PAUSE auction is one of a few efforts to release the auctioneer from having to do all the work. The pausebid bidding algorithm generates myopically-optimal bids for agents in a PAUSE auction but its running time is exponential on the number of bids. We present new approximate bidding algorithms that not only run in linear time but also increase the utility of the bidders as result of small decrement in revenue.
Abstract: The agents in multiagent systems can coordinate their actions and handle tasks jointly by forming coalitions. One of the important steps in this process is the fair division of payoff generated from such a joint effort among all coalition members. The nucleolus is widely recognized as a fair way of distributing the revenue in a coalition. While we have efficient algorithms for computing the nucleolus using linear programming based techniques, we believe that such approaches are infeasible in multiagent settings where the loci of decision making is distributed among all agents in the system, and there is no central agent that can aggregate all data and compute for all agents. Towards this end, in this paper we present a distributed algorithm that computes the nucleolus-stable payoff division for any multiagent system modeled as a characteristic form game. We empirically show that our algorithm has many desirable properties -- it searches only a small fraction of the solution space, evenly distributes the computational load among all agents, and executes reasonably quickly for this hard problem.
Abstract: In this study we examine the relationship between supply network’s topology and its robustness, responsiveness and dynamism in the presence of random and targeted attacks. The investigation uses the theoretical and modeling framework proposed in Sterman (1988) as the basis for examining adaptive behavior in an inventory management decision context. The linear supply chain in Sterman (1988) is extended to form supply networks that have distinct topological characteristics. Specifically, the two dominant topological paradigms of random networks and scale-free networks are considered to form supply networks. The robustness, responsiveness and dynamism of these networks are examined by considering random node failures and targeted attacks on nodes. The study considers supply chain performance measures, such as inventory levels and cost, as well as network performance measures, such as characteristic path length, size and length of largest connected component, maximum distance in the largest connected component and clustering coefficients. Based on the findings of these computational experiments we develop several research propositions that would potentially enable further theory development of complex adaptive supply networks.
Abstract: The asynchronous searching techniques are characterized by the fact that each agent instantiates its variables in a concurrent way. Then, it sends the values of its variables to other agents directly con- nected to it by using messages. These asynchronous techniques have di®erent behaviors in case of delays in sending messages. This article depicts the opportunity for synchronizing agents' execution in case of asynchronous techniques. It investigates and compares the behaviors of several asynchronous techniques in two cases: agents process the received messages asynchronously (the real situation from practice) and the syn- chronous case, when a synchronization of the agents' execution is done i.e. the agents perform a computing cycle in which they process a mes- sage from a message queue. After that, the synchronization is done by waiting for the other agents to ¯nalize the processing of their messages. The experiments show that the synchronization of the agents' execution leads to lower costs in searching for solution. A solution for synchro- nizing the agents' execution is proposed for the analyzed asynchronous techniques.
Abstract: Distributed allocation and multiagent coordination problems can be solved through combinatorial auctions. However, most of the existing winner determination algorithms for combinatorial auctions are centralized. The PAUSE auction is one of a few efforts to release the auctioneer from having to do all the work (it might even be possible to get rid of the auctioneer). It is an increasing price combinatorial auction that naturally distributes the problem of winner determination amongst the bidders in such a way that they have an incentive to perform the calculation. It can be used when we wish to distribute the computational load among the bidders or when the bidders do not wish to reveal their true valuations unless necessary. PAUSE establishes the rules the bidders must obey. However, it does not tell us how the bidders should calculate their bids. We have developed a couple of bidding algorithms for the bidders in a PAUSE auction. Our algorithms always return the set of bids that maximizes the bidder's utility. Since the problem is NP-Hard, run time remains exponential on the number of items, but it is remarkably better than an exhaustive search. In this paper we present our bidding algorithms, discuss their virtues and drawbacks, and compare the solutions obtained by them to the revenue-maximizing solution found by a centralized winner determination algorithm.
Abstract: Most of the research on multiagent systems has focused on the development of rational utility-maximizing agents. However, research shows that emotions have a strong effect on peoples' physical states, motivations, beliefs, and desires. By introducing primary and secondary emotion into BDI architecture, we present a generic architecture for an emotional agent, EBDI, which can merge various emotion theories with an agent's reasoning process. It implements practical reasoning techniques separately from the specific emotion mechanism. The separation allows us to plug in emotional models as needed or upgrade the agent's reasoning engine independently.
Abstract: Coalition formation is an important form of interaction in multiagent systems. It enables the agents to satisfy tasks that they would otherwise be unable to perform, or would perform with a lower efficiency. The focus of our work is on real-world application domains where we have systems inhabited by rational, self-interested agents. We also assume an environment without any trusted central manager to resolve issues concerning multiple agents. For such environments, we have to determine both an optimal (utility-maximizing) coalition configuration and a stable payoff configuration, concurrently and in a distributed fashion. Solving each of these problems is known to be computationally expensive, and having to consider them together exacerbates the problem further. In this paper, we present our Progressive, Anytime, Convergent, and Time-efficient (PACT) algorithm for coalition formation to address the above concerns. We assess the stability of the resulting coalition by using a new stability concept, the relaxed core, which is a slight variation on the core. We show experimentally that our algorithm performs admirably in comparison to an optimal solution, it typically produces solutions that are relaxed-core-stable, and it scales well.
Abstract: We are developing a mobile handheld system that provides tactical and cultural advice to warfighters. The system fuses built-in knowledge of social factors and location specific information with dynamically entered situation descriptions to produce an assessment of the situation and recommend actions. The outcomes include the system’s confidence in its recommendations, along with explanations of its reasoning. The result gives warfighters the information they need to make the critical decisions necessary to accomplish their mission, while minimizing the collateral damage that alienates the local populace.
Abstract: A multiagent systems textbook which emphasizes the game theoretical foundations of multiagent research and combines them with hands-on experimentation of system dynamics using NetLogo sample programs. This textbook is a work in progress.
Abstract: This paper presents the Emotional-Belief-Desire-Intention architecture which reflects humans' practical reasoning by adding the influence of primary and secondary emotions into the decision making process of a traditional BDI architecture. Our architecture handles bounded resources by using primary emotions as the first filter for adjusting the priority of beliefs, thereby allowing the agents to speed up decision making. Secondary emotions are used to refine the decision when time permits. We present a sample EBDI agent for the Tileworld domain in order to show our architecture might be used.
Abstract: Combinatorial auctions are a great way to represent and solve distributed allocation problems. Unfortunately, most of the winner determination solutions that exists are centralized. They require all agents to send their bids to a centralized auctioneer who then determines the winners. The PAUSE auction, in contrast, is an increasing-price combinatorial auction in which the problem of winner determination is naturally distributed amongst the bidders. Furthermore, the bidders' have an incentive to perform the required computations. But, until now, no bidding algorithm for the auction existed. We provide a bidding algorithm for agents in a PAUSE auction, the pausebid algorithm. It always returns the bid that maximizes the bidder's utility. In effect, pausebid is a the distributed counterpart to the existing centralized winner determination algorithms, from which we borrow several proven techniques. Our test results show that a system where all agents use pausebid finds the revenue-maximizing solution at least 95\% of the time. Run time, as expected since this is an NP-complete problem, remains exponential on the number of items.
Abstract: We introduce an emotional agent model that shows how emotions affect an agent's negotiation strategy. By adding emotions, we add the effects of these indirectly related features to the negotiation, features that are ignored in most models. Our new method, the PAD Emotional Negotiation Model, maps a nonemotional agent's strategy during negotiation to the strategy used by an emotional agent. Our evaluations show this model can be used to implement agents with various emotional states that mimic human emotions during negotiation.
Abstract: The problem of optimal winner determination in combinatorial auctions consists of finding the set of bids that maximize the revenue for the sellers. Various solutions exist for solving this problem but they are all centralized. That is, they assume that all bids are sent to a centralized auctioneer who then determines the winning set of bids. In this paper we introduce the problem of distributed winner determination in combinatorial auctions which eliminates the centralized auctioneer. We present a set of distributed search-based algorithms for solving this problem and study their relative tradeoffs.
Abstract: We provide a summary of the lessons we have learned after teaching a graduate multiagent systems class over the last six years. The class has used various technologies such as RoboCup (along with our Biter and SoccerBeans tools), NetLogo, JADE, and FIPA-OS. We discuss their advantages and disadvantages. We also discuss our view of the future of multiagent systems. We notice the ongoing separation of software agent design from the theoretical underpinnings of multiagent theory and propose the development of a unifying notation for representing multiagent problems.
Abstract: Advances in Information Technology have created opportunities for business enterprises to redesign their information and process management systems. The redesigned systems will likely employ some form of workflow management system. Workflow management systems exactly enact business processes described in a process description language. Unfortunately, such strict adherence to the prescribed workflow makes it impossible for the system to adapt to unforeseen circumstances. We firmly believe that the historic trajectory of software development paradigms and IT advancements will establish multiagent systems as the workflow enactment mechanism of the future. In this paper we provide a critical survey of workflow, workflow description languages, web services and agent technologies. We propose that workflow description languages and their associated design tools can be used to specify a multiagent system. Specifically, we advance the idea that the Business Process Execution Language for Web Services (BPEL4WS) can be used as a specification language for expressing the initial social order of the multiagent system, which can then intelligently adapt to changing environmental conditions.
Abstract: We study the problem of distributed workflow enactment in which new job requests, each composed of a workflow, a deadline, and a payment, arrive at a company at regular intervals. The company must decide which services to perform in which workflows and with which service agents. It must also provide the proper monetary incentives to its selfish service agents so as to align their interests with those of the company. In this scenario we evaluate various pricing strategies and show that an adaptive pricing mechanism is required because it is a dominant strategy and it increases revenue.
Abstract: The problem of optimal winner determination in combinatorial auctions consists of finding the set of bids that maximize the revenue for the sellers. Various solutions exist for solving this problem but they are all centralized. That is, they assume that all bids are sent to a centralized auctioneer who then determines the winning set of bids. In this paper we introduce the problem of distributed winner determination in combinatorial auctions which eliminates the centralized auctioneer. We present a set of distributed search-based algorithms for solving this problem and study their relative tradeoffs.
Abstract: We show how the Asynchronous Backtracking Algorithm, a well known distributed constraint satisfaction algorithm, produces unnecessary messages. Our new optimized algorithm reduces the number of messages by implementing message management mechanism. Tests show our algorithm significantly reduces the total number of messages sent and drastically reduces the number of cycles used when solving instances of the graph coloring problem.
Abstract: We present a domain model and protocol for the exchange of recommendations by selfish agents without the aid of any centralized control. Our model captures a subset of the realities of recommendation exchanges in the Internet. We provide an algorithm that selfish agents can use for deciding whether to exchange recommendations and with whom. We analyze this algorithm and show that, under certain common circumstances, the agents' rational choice is to exchange recommendations. Finally, we have implemented our model and algorithm and tested the performance of various populations. Our results show that both the social welfare and the individual utility of the agents is increased by participating in the exchange of recommendations.
Abstract: We present our Component-Based Agent Framework, which enables a software engineer to design a set of agents by using a visual component-based toolkit (Sun's BDK), and wiring together desired blocks of functionality. We instantiate this framework in the RoboCup domain by implementing the necessary components. The implementation also serves as a proof of the viability of our framework. Finally, we use this implementation to build sample agents. The proposed framework is a first step towards the merging of agent-based and component-based design tools.
Abstract: We study the benefits of teaming and selflessness when using multiagent search to solve task-oriented problems. We start by presenting a formal framework for multiagent search which, we show, forms a superset of the task-oriented domain, coalition formation, distributed constraint satisfaction, and $NK$ landscape search problems. We focus on task-oriented domain problems and show how the benefits of teaming and selflessness arise in this domain. These experimental results are compared to similar results in the $NK$ domain—from which we import a predictive technique. Namely, we show that better allocations are found when the dynamics of the multiagent system lie between order and chaos. Several other specific findings are presented such as the fact that neither absolute selfishness nor absolute selflessness result in better allocations, and the fact that the formation of small teams usually leads to better allocations.
Abstract: Industry and researchers have two different visions for the future of Web services. Industry wants to capitalize on Web service technology to automate business processes via centralized workflow enactment. Researchers are interested in the dynamic composition of Web services. The authors show how these two visions are two points in a continuum and discuss a possible path for bridging the gap between them.
Abstract: We describe the lessons learned from using various technologies as aids in teaching a graduate multiagent systems class. The class has been offered six times over the last five years. The technologies described are RoboCup (along with our Biter and SoccerBeans tools), NetLogo, JADE, and FIPA-OS. We also discuss our view of the future of multiagent systems which includes the separation of software agent design into a separate class that focuses on distributed programming and the development of a unifying notation for representing multiagent problems.
Abstract: This paper describes our development of a distributed, functionally equivalent agent-based workflow enactment mechanism from a BPEL4WS specification. This work demonstrates that BPEL4WS can be viewed as a description of the social order of a collection of agents, where the agents serve as proactive proxies for the underlying passive Web services. Although the Semantic Web initiative is working toward semantically rich descriptions of Web services, which can be reasoned about by agents, the current state-of-the-art does not yet allow for collections of agents representing semantic Web services to organize themselves to enact workflows. Therefore, this work is critically important as it serves as a bridge from existing, static views of workflow enactment to future, agent-based, dynamic workflow engines.
Abstract: The ability to dynamically bind to Web services at runtime is becoming increasingly important as the era of Service-Oriented Computing (SOC) emerges. With SOC selection and invocation of Web service partners will occur in software at run-time, rather than by software developers at design and compile time. Unfortunately, the marketplace has yet to yield a predominate applications programming interface for the invocation of Web services. This results in software that is deeply ingrained with vendor-specific calls. This is problematic because Web service technology is changing at a rapid pace. In order to leverage the latest developments, code often needs to be heavily refactored to account for changing invocation interfaces. This paper explores the mitigation of this problem through the application of software design patterns. Specifically, it details how a Web service architectural pattern, based upon the composition of software design patterns, provides for implementations that insulate the application code from the peculiarities of any specific vendor's interface.
Abstract: In the future, Web services and software agents will coexist in the Business Process Management solution space. In our vision, agents will have symbiotic relationships with Web services, harnessing them as externally defined agent behaviors. In this paper we detail the development of a demonstration system that transparently integrates agent services into BPEL4WS defined workflows. The development of the demonstration system illustrates the power of compositional approaches to system creation. It also serves to reinforce the importance of open standards, since the integration of the separate components is dependent upon the interoperability that standards provide. This work is an important first step toward fully integrated agent-based workflow management systems.
Abstract: We describe a framework and equations used to model and predict the behavior of multi-agent systems (MASs) with learning agents. A difference equation is used for calculating the progression of an agent's error in its decision function, thereby telling us how the agent is expected to fare in the MAS. The equation relies on parameters which capture the agent's learning abilities, such as its change rate, learning rate and retention rate, as well as relevant aspects of the MAS such as the impact that agents have on each other. We validate the framework with experimental results using reinforcement learning agents in a market system, as well as with other experimental results gathered from the AI literature. Finally, we use PAC-theory to show how to calculate bounds on the values of the learning parameters
Abstract: We describe a technique for providing agent software with dynamically configured capabilities. These capabilities, described with DAML-S, can represent atomic or orchestrated Web Services. The DAML-S specification will be transformed into an executable program written in a composition language named Piccola. When executed, the composite service will be available as a semantically described behavior within a FIPA compliant agent.
Abstract: Distributed Internet-based attacks on computer systems are becoming more prevalent. These attacks usually employ some form of automation and involve the compromise of many systems across the Internet; systems which are not necessarily owned by the same company or individual. The information needed to detect and neutralize these attacks is spread across many machines. A system administrator who wishes to detect and handle these distributed attacks must constantly monitor his systems and communicate with other administrators around the world—a challenging task. In this paper we present our design and implementation of a multi-agent system, built using FIPA-OS, in which agents responsible for different network realms communicate with each other in order to determine if certain suspicious events are actually part of a distributed attack, and to warn each other about possible threats. We describe the event types which, we have found, flag the presence of suspicious activities and trigger the agents into action. We explain the various interaction protocols that we have implemented in order to handle these suspicious events. We discuss issues and requirements involved in standardizing formats and architectures for the distributed management of intrusion detection. Finally, we present the results of some of the tests we have performed on our system.
Abstract: DAML-S provides the means for a web service to advertise its functionality to potential users of the service. This brings to fore the issue of discovering an advertisement that best matches a request for a particular service a process referred to as matchmaking. The algorithms that have thus far been proposed for matchmaking are based on comparisons of the requested and offered inputs and outputs. In this project, we extend these algorithms by taking into account the detailed process description of the service, thus leading to more accurate matchmaking. That is, we present an algorithm that will allow users to find services based on their Service Model Description. The query language we introduce supports both positive and negative terms. The algorithm runs in worst time of O($c^n$ ), where c is the number of process nodes in the advertisement and n is the number of outputs to be matched. We also show results of tests performed against a simple database.
Abstract: Our research is concerned with the study and development of incentive-compatible exchange mechanisms for recommendations in a multiagent system. These mechanism will allow and motivate agents to create an economy of ideas, where agents trade recommendations between themselves. In this paper we present a domain model and an incentive-compatible protocol for information exchange. Our model captures a subset of the realities of recommendation exchanges in the Internet. We provide an algorithm that selfish agents can use for deciding whether to exchange recommendations and with whom. We analyze this algorithm and show that, under certain common circumstances, the agents' rational choice is to exchange recommendations. Finally, we have implemented our model and algorithm and tested the performance of various populations. Our results show that both the social welfare and the individual utility of the agents is increased by participating in the exchange of recommendations.
Abstract: We introduce the topic of learning in multiagent systems. We first provide a quick introduction to the field of game theory, focusing on the equilibrium concepts of iterated dominance, and Nash equilibrium. We show some of the most relevant findings in the theory of learning in games, including theorems on fictitious play, replicator dynamics, and evolutionary stable strategies. The CLRI theory and n-level learning agents are introduced as attempts to apply some of these findings to the problem of engineering multiagent systems with learning agents. Finally, we summarize some of the remaining challenges in the field of learning in multiagent systems.
Abstract: Workflow management systems exactly enact business processes described in a process description language. Unfortunately, such strict adherence to the prescribed workflow makes it impossible for the system to adapt to unforeseen circumstances. In this paper we propose that workflow description languages and their associated design tools can be used to specify a multiagent system. Specifically, we advance the idea that the Business Process Execution Language for Web Services can be used as a specification language for expressing the initial social order of a multiagent system, which can then intelligently adapt to changing environmental conditions.
Abstract: We present a method for solving service allocation problems in which a set of services must be allocated to a set of agents so as to maximize a global utility. The method is completely distributed so it can scale to any number of services without degradation. We first formalize the service allocation problem and then present a simple hill-climbing, a global hill-climbing, and a bidding-protocol algorithm for solving it. We analyze the expected performance of these algorithms as a function of various problem parameters such as the branching factor and the number of agents. Finally, we use the sensor allocation problem, an instance of a service allocation problem, to show the bidding protocol at work. The simulations also show that phase transition on the expected quality of the solution exists as the amount of communication between agents increases.
Abstract: Today s software systems are becoming more net-centric, distributed, and heterogeneous. Hardware, software and networking technology will combine in a milieu in which they become ubiquitous and inseparable. The acceleration of technology and time-to-market pressures make it increasingly difficult to produce software. In order to achieve the promise of the information age, software developers will require new abstractions that will allow them to manage the overwhelming complexity of this digital landscape. This short position paper describes a novel technique that will imbue agent software with dynamically configured capabilities. These capabilities, described with DAML-S, can represent atomic or orchestrated Web Services. The DAML-S specification will be transformed into an executable program written in a composition language named Piccola. When executed, the composite service will be available as a semantically described behavior within a FIPA compliant agent. The proposed architecture is designed for scalability, from mobile PDA devices with wireless connectivity to resource-rich server class systems.
Abstract: This paper describes a security framework in distributed systems where an Intelligent Agent handles the security monitoring at each host. The agents are made responsible for alerting the system administrators about an attempted intrusion or misuse for a particular system. Recently, there has been an increase in the number of reports of the attacks, which are wide spread across the network and affecting a chain of systems before they attack the actual target system. To detect such attacks, the amount of information associated within a single isolated system is inadequate for an agent to confirm an intrusion. Therefore, the need for a framework that allows the agents to negotiate with their co-agents to share information about an intrusion, thereby aiding in effective handling of Intrusion Detection is emphasized. Our design aims at developing such a framework in the FIPA-OS (Foundation for Intelligent Physical Agents ? Open Source) environment, which provides most of the source code for building agents on its platform. The concept of mutual co-operation among agents has been developed as a means of queries. These queries are carried out by tasks associated with each agent. The protocols to support these interactions by means of queries are explained. The issues and requirements involved in standardizing formats, interaction protocols and architectures to co-manage intrusion detection are discussed.
Abstract: We present our experiences using the RoboCup soccerserver simulator and Biter, our own agent platform, for the teaching of a graduate multiagent systems' class. The RoboCup simulator and Biter are both described. We argue that the combination of RoboCup and Biter forms an effective platform for the teaching of multiagent systems and the distributed mindset. Results from two semesters using these tools are presented. These results confirm our claims. Finally, we characterize this work within the framework provided by the STEELMAN Draft of the Computing Curricula 2001 initiative.
Abstract: We introduce Biter, a platform for the teaching and research of multiagent systems' design. Biter implements a client for the RoboCup simulator. It provides users with the basic functionality needed to start designing sophisticated RoboCup teams. Some of its features include a world model with absolute coordinates, a graphical debugging tool, a set of utility functions, and a Generic Agent Architecture (GAA) with some basic behaviors such as ``dribble ball to goal'' and ``dash to ball''. The GAA incorporates an elegant object-oriented design meant to handle the type of activities typical for an agent in a multiagent system. These activities include reactive responses, long-term behaviors, and conversations with other agents. We also discuss our initial experiences using Biter as a pedagogical tool for teaching multiagent systems' design.
Abstract: We introduce the Generic Agent Architecture (GAA) along with Biter—an implementation of our GAA for the RoboCup domain. The GAA incorporates an elegant object-oriented design meant to handle the type of activities typical for an agent in a multiagent system. These activities include reactive responses, long-term behaviors, and conversations with other agents. We also show how small modifications in the GAA implementation can lead to a subsumption agent or to a BDI agent. Finally, we present our Biter implementation as a proof of concept and use it to illustrate the added functionality that a user of the GAA must implement in a specific domain in order to utilize our GAA.
Abstract: Multiagent-system platforms aid in creating agent-based systems, but to use them effectively we must understand an agent's architecture.
Abstract: We show how to build agents that learn about agents in Multi-Agent Systems (MAS) composed of similar learning agents. The problem is divided into the two subproblems of deciding how much an agent should think about what others think about what others think\ldots and the problem raised by the fact that if the other agents are learning and changing their behavior, an agent's model of them might never be accurate. We start by presenting a framework that can formally describe a MAS and the agents that inhabit it, along with their behavior and a measure of the correctness of this behavior. The framework is used to develop an algorithm (LR-RMM) that tells an agent when to stop thinking about other agents. The algorithm is implemented and its results verified. The framework is then extended to capture the agents' learning abilities and the degree to which they impact each others' behavior. This extended framework (CLRI) is used to predict the expected behavior of learning agents in MASs. Theoretical predictions from this framework are confirmed with experimental results from our research and with experimental results from the research literature. Finally, a specific market-based MAS is studied in detail. We confirm results predicted by the CLRI framework and present other findings specific to market-based MAS. These findings include the fact that learning agents make the system more robust to the presence of malicious agents, and the fact that agents can expect decreasing returns for increasing levels of strategic thinking.
Abstract: We present our approach to the problem of how an agent, within an economic Multi-Agent System, can determine when it should behave strategically (i.e. learn and use models of other agents), and when it should act as a simple price-taker. We provide a framework for the incremental implementation of modeling capabilities in agents, and a description of the forms of knowledge required. The agents were implemented and different populations simulated in order to learn more about their behavior and the merits of using and learning agent models. Our results show, among other lessons, how savvy buyers can avoid being ``cheated'' by sellers, how price volatility can be used to quantitatively predict the benefits of deeper models, and how specific types of agent populations influence system behavior.
Abstract: We describe a framework that can be used to model and predict the behavior of MASs with learning agents. It uses a difference equation for calculating the progression of an agent's error in its decision function, thereby telling us how the agent is expected to fare in the MAS. The equation relies on parameters which capture the agents' learning abilities (such as its change rate, learning rate and retention rate) as well as relevant aspects of the MAS (such as the impact that agents have on each other). We validate the framework with experimental results using reinforcement learning agents in a market system, as well as by other experimental results gathered from the AI literature.
Abstract: We provide a framework for the study of learning in certain types of multi-agent systems (MAS), that divides an agent's knowledge about others into different ``types''. We use concepts from computational learning theory to calculate the relative sample complexities of learning the different types of knowledge, given either a supervised or a reinforcement learning algorithm. These results apply only for the learning of a fixed target function, which would probably not exist if the other agents are also learning. We then show how a changing target function affects the learning behaviors of the agents, and how to determine the advantages of having lower sample complexity. Our results can be used by a designer of a learning agent in a MAS to determine which knowledge he should put into the agent and which knowledge should be learned by the agent.
Abstract: We present our approach to the problem of how an agent, within an economic Multi-Agent System, can determine when it should behave strategically (i.e. model the other agents), and when it should act as a simple price-taker. We provide a framework for the incremental implementation of modeling capabilities in agents. These agents were implemented and different populations simulated in order to learn more about their behavior and the merits of using agent models. Our results show, among other lessons, how savvy buyers can avoid being ``cheated'' by sellers, how price volatility can be used to quantitatively predict the benefits of deeper models, and how specific types of agent populations influence system behavior.
Abstract: We present an algorithm that an agent can use for determining which of its nested, recursive models of other agents are important to consider when choosing an action. Pruning away less important models allows an agent to take its ``best'' action in a timely manner, given its knowledge, computational capabilities, and time constraints. We describe a theoretical framework, based on \em situations, for talking about recursive agent models and the strategies and expected strategies associated with them. This framework allows us to rigorously define the \em gain of continuing deliberation versus taking action. The expected gain of computational actions is used to guide the pruning of the nested model structure. We have implemented our approach on a canonical multi-agent problem, the pursuit task, to illustrate how real-time, multi-agent decision-making can be based on a principled, combinatorial model. Test results show a marked decrease in deliberation time while maintaining a good performance level.
Abstract: Research in distributed AI has dealt with the interactions of agents' both cooperative and self-interested. The Recursive Modeling Method (RMM) is one method used for modeling rational self-interested agents. It assumes that knowledge is nested to a finite depth. An expansion of RMM using a sigmoid function was proposed with the hope that the solution concept of the new RMM would approximate the Nash EP in cases where RMMS knowledge approximated the common knowledge that is assumed by game theory. In this paper, we present a mathematical analysis of RMM with the sigmoid function and prove that it indeed tries to converge to the Nash EP. However, we also show how and why it fails to do so for most cases. Using this analysis we argue for abandoning the sigmoid function as an implicit representation of uncertainty about the depth of knowledge in favor of an explicit representation of the uncertainty. We also suggest other avenues of research that might give us other more efficient solution concepts which would also take into consideration the cost of computation and the expected gains.
Student ratings given for Instructor/department/college: