Search

The increase in the amount of traffic caused by economic growth in recent years is taking its toll on the infrastructure and the environment. The transportation sector is faced with a suboptimum in haulage because trucks drive empty 40-60% of the time on the average. This is caused by the large number of planning variables, the restrictions and dynamics of external factors, market diffusion and a relatively low level of automation. The constantly advancing ICT technology can reduce this suboptimum. The aim of DEAL has been to speed up negotiations between different parties by using representation through software agents, increasing the number of examined alternatives as a result. The use of software agents also allow for an unlimited number of stakeholders to take part in negotiations, generating an overall optimal solution. With a higher level of detail of the information used in negotiations, such as specific location and remaining driving time, a better deal can be offered. Reducing the percentage of empty trucks has a significant effect on the environment as well. The amount of goods being moved remains the same, but the necessary mileage is strongly reduced. This leads to less CO2 emission, which contributes to the realization of the Kyoto treaty commitments. A side effect of the reduction in transportation movements is the improvement of mobility as a whole. DEAL is a research project depending on the collaboration between commercial and research parties. Within the present consortium, wide experience is present on both the technological aspects and the market in focus. The ambition of the consortium is to apply the attained knowledge on a broad scale in products destined for the national and international logistic services. The consortium consists of Vos Logistics, Post-Kogeko, Carrierweb, Erasmus University Rotterdam, Free University of Amsterdam, Radboud university Nijmegen, Centre for Mathematics and Computer Science and Almende.

Negotiations are an important way of reaching agreements between selfish autonomous agents. In this paper we focus on one-to-many bargaining within the context of agent-mediated electronic commerce. We consider an approach where a seller negotiates over multiple interdependent attributes with many buyers individually. Bargaining is conducted in a bilateral fashion, using an alternating-offers protocol. In such a one-to-many setting, “fairness,” which corresponds to the notion of envy-freeness in auctions, may be an important business constraint. For the case of virtually unlimited supply (such as information goods), we present a number of one-to-many bargaining strategies for the seller, which take into account the fairness constraint, and consider multiple attributes simultaneously. We compare the performance of the bargaining strategies using an evolutionary simulation, especially for the case of impatient buyers and small premature bargaining break off probability. Several of the developed strategies are able to extract almost all the surplus; they utilize the fact that the setting is one-to-many, even though bargaining occurs in a bilateral fashion.

We adapt the Model-Based Diagnosis framework to perform (agent-based) plan diagnosis. In plan diagnosis, the system to be diagnosed is a plan, consisting of a partially ordered set of instances of actions, together with its executing agent. The execution of a plan can be monitored by making partial observations of the results of actions. Like in standard model-based diagnosis, observed deviations from the expected outcomes are explained qualifying some action instances that occur in the plan as behaving abnormally. Unlike in standard model-based diagnosis, however, in plan diagnosis we cannot assume that actions fail independently. We focus on two sources of dependencies between failures: dependencies that arise as a result of a malfunction of the executing agent, and dependencies that arise because of dependencies between action instances occurring in a plan. Therefore, we introduce causal rules that relate health states of the agent and health states of actions to abnormalities of other action instances. These rules enable us to introduce causal set and causal effect diagnoses that use the underlying causes of plan failing to explain deviations and to predict future anomalies in the execution of actions.

We discuss the application of Model Based Diagnosis in agent-based planning. We model a plan as a system to be diagnosed and assume that agents can monitor the execution of the plan by making partial observations during plan execution. These observations are used by the agents to explain plan deviations (errors) by qualifying some action instances as behaving abnormally. We prefer those qualifications that are maximum informative, i.e. explain as much as possible. Since in a plan several instances of the same action might occur, an error occurring in one instance might be used to predict the occurrence of the same error in an action instance to be executed later on. To account for such correlations, we introduce causal rules to generate diagnoses from action instances qualified as abnormally and we introduce Pareto minimal causal diagnoses as the right extension of classical minimal diagnoses.Next, we consider the multi-agent perspective where each agent is responsible for a part of the total plan, we show how plan-diagnoses of these partial plans are related to diagnoses of the total plan and how global diagnoses can be obtained in a distributed way.

Agent-based computational economics (ACE) combines elements from economics and computer science. In this paper, the authors focused on the relation between the evolutionary technique that is used and the economic problem that is modeled. In the field of ACE, economic simulations often derive parameter settings for the genetic algorithm directly from the values of the economic model parameters. In this paper, two important approaches that are dominating in ACE were compared and showed that the above practice may hinder the performance of the GA and thereby hinder agent learning. More specifically, it is shown that economic model parameters and evolutionary algorithm parameters should be treated separately by comparing the two widely used approaches to social learning with respect to their convergence properties and robustness. This leads to new considerations for the methodological aspects of evolutionary algorithm design within the field of ACE. Improved social (ACE) simulation results were also presented for the Cournot oligopoly game, yielding (higher profit) Cournot-Nash equilibria instead of the competitive equilibria.

We investigate the spread of innovations on a social network. The network consists of agents that are exposed to the introduction of a new product. Consumers decide whether or not to buy the product based on their own preferences and the decisions of their neighbors in the social network. We use and extend concepts from the literature on epidemics and herd behavior to study this problem. The central question of this paper is whether firms can learn about the network structure and consumer characteristics when only limited information is available, and use this information to evolve a successful directed-advertising strategy. In order to do so, we extend existing models to allow for heterogeneous agents and both positive and negative externalities. The firm can learn a directed-advertising strategy that takes into account both the topology of the social consumer network and the characteristics of the consumer. Such directed-advertising strategies outperform random advertising.

This position paper outlines possible research directions related to market-based methods, especially as they apply to logistic settings. First, we describe some of the characteristics of the logistics domain. Next, we identify and discuss some fundamental research problems which we consider open and relevant for this domain, from the agent-based electronic markets perspective.

Reputation mechanisms allow agents to establish trust in other agents’ intentions and capabilities in the absence of direct interactions. In this paper, we are concerned with establishing trust on the basis of reputation information in open, decentralized systems of interdependent autonomous agents. We present a completely decentralized reputation mechanism to increase the accuracy of agents’ assessments of other agents’ capabilities and allow them to develop appropriate levels of trust in each other as providers of reliable information. Computer simulations show the reputation system’s ability to track an agent’s actual capabilities. The work described in this paper was performed in the context of the cim project on Cybernetic Incident Management, sponsored by the Dutch government (senter) as project number TSIT2021. See http://www.almende.com/cim/ for more information. We are grateful to Floortje Alkemade, Pınar Yolum and Pieter Jan ’t Hoen for stimulating discussions, and to three anonymous referees for helpful comments.

Electronic commerce and trading of information goods significantly impact the role of intermediaries: consumers can bypass intermediating agents by forming direct links to producers. One reason that traditional intermediaries can still make a profit, is that they have more knowledge of the market, so trading via an intermediary saves on search costs [1], allowing the intermediary to charge a markup and make a profit. Another reason is trust and loyalty between consumers and intermediaries (cf. [6]). In this paper we investigate whether trust-based intermediating agents will also be able to make a profit in electronic markets, where other advantages of intermediaries (i.e., advantages of location or scale) disappear, but where trust and reputation mechanisms are becoming popular for helping consumers make purchasing decisions in the face of information overload on the world wide web [2]. We model an electronic market where agents trade an information good over a network. Buyer-agents use a decentralized reputation-based trust mechanism [4] to determine which connections to maintain to sellers of the good (producers and intermediaries), communicating with each other to establish trustworthiness of sellers to which they are not currently connected. The existence of such a reputation mechanism allows intermediating agents to accumulate a base of loyal consumer-agents who are willing to pay the intermediaries' markup in exchange for the intermediating agents' protection against the dynamics of the market place. Using computer simulations, we show that if market dynamics are sufficiently complex, trusted intermediaries are able to increase their market share and make a profit.

We discuss task planning problems where a number of agents have to work on a joint planning problem that consists of a set of interdependent, hierarchically ordered tasks. Each agent is assigned a subset of tasks to perform for which it has to construct a plan. The agents are non-cooperative in that they insist on planning autonomously and do not want to revise their individual plans when a joint plan has to be assembled. The aim of this paper is twofold: first of all to present a general formal framework to study some computational aspects of this non-cooperative coordination problem, and secondly to establish some complexity results and to identify some of the factors that contribute to the complexity of this problem.

For various e-commerce applications autonomous agents can do the actual trading on behalf of their users. We consider an agent who trades repeatedly on behalf of his user, given an overall budget and preferences per time step, both specified at the start. For many e-commerce settings such an agent has limited computational resources, limited prior information concerning price fluctuations, and little time for online learning. We therefore develop an efficient heuristic that requires little prior information to work well from the start, even for very roughed nonsmooth problem instances. Extensive computer experiments conducted for a wide variety of customer preferences show virtually no difference in performance between a dynamic programming (DP) approach and the developed heuristic carrying out the agent's task. The DP approach has, however, the important drawback of generally being too computationally intensive.

Large memories have become an affordable storage medium for databases involving hundreds of Gigabytes on multi-processor systems. In this short note, we review our research on building relational engines to exploit this major shift in hardware perspective. It illustrates that key design issues related to parallelism pose architectural problems at all levels of a system architecture and whose impact is not easily predictable. The sheer size/complexity of a relational DBMS and the sliding requirements of frontier applications are indicative that a substantial research agenda remains wide open.

In this paper, we present a system that combines independent feature detector programs with multimedia database technology to provide a semantic rich index to multimedia data items on the World Wide Web. First, we introduce a grammatical framework, called feature grammars, which forms the indexing schema. Feature grammars are an extension of context-free grammars with active symbols (e.g., multimedia feature detectors) that may invoke feature detector programs. The Acoi system reads in the grammar, compiles it and executes it against a data source, e.g. a multimedia object. The derived parse tree is used as an index to this data source. Its structure closely resembles that of semi-structured (XML) documents. Then, we present the architecture of our implementation on top of Monet, our extensible main memory database system. In this implementation, feature grammars are used as a description of the execution sequence of the indexing program. We show how the resulting parse tree can be stored efficiently in Monet. A SQL-like query language enables users to use the feature grammar as a schema for query formulation to retrieve both index values and the original data sources. Throughout the paper, we illustrate the concepts with a running example of a grammar used for indexing HTML pages and multimedia objects on the World Wide Web.

In query-intensive database application areas, like decision support and data mining, systems that use vertical fragmentation have a significant performance advantage. In order to support relational or object oriented applications on top of such a fragmented data model, a flexible yet powerful intermediate language is needed. This problem has been successfully tackled in Monet, a modern extensible database kernel developed by our group. We focus on the design choices made in the Monet Interpreter Language (MIL), its algebraic query language, and outline how its concept of tactical optimization enhances and simplifies the optimization of complex queries. Finally, we summarize the experience gained in Monet by creating a highly efficient implementation of MIL.

In the past decade, advances in speed of commodity CPUs have far out-paced advances in memory latency. Main-memory access is therefore increasingly a performance bottleneck for many computer applications, including database systems. In this article, we use a simple scan test to show the severe impact of this bottleneck. The insights gained are translated into guidelines for database architecture; in terms of both data structures and algorithms. We discuss how vertically fragmented data structures optimize cache performance on sequential data access. We then focus on equi-join, typically a random-access operation, and introduce radix algorithms for partitioned hash-join. The performance of these algorithms is quantified using a detailed analytical model that incorporates memory access cost. Experiments that validate this model were performed on the Monet database system. We obtained exact statistics on events like TLB misses, L1 and L2 cache misses, by using hardware performance counters found in modern CPUs. Using our cost model, we show how the carefully tuned memory access pattern of our radix algorithms make them perform well, which is confirmed by experimental results.

With the increasing popularity of WWW, the main challenge in computer science has become content-based retrieval of multimedia objects. Until now access of multimedia objects in databases was done by means of keywords. Now, with the integration of feature-detection algorithms in database systems software, content-based retrieval can be fully integrated with query processing. In this paper, we describe our experimentation platform under development that fully integrates traditional query processing and content-based retrieval and that is based on feature databases, making database technology available to multimedia.

Database applications using large vector data are often supported by spatial index structures to locate spatially related objects. An important query class deals with finding related object pairs under a distance function. %, i.e. those %spatially close to a given point. , like nearest neighbors. In this paper we demonstrate that a light-weight indexing structure, based on the metric properties derived from the distance function, is often sufficient to support this important class. It is of particular importance as a temporary search accelerator while processing complex queries. Moreover, it can be used to speed up point and region queries for low selectivities and, presumably, highly-skewed spaces.

A key assumption underlying query optimization schemes for parallel processing is that their cost models can anticipate the multitude of effects encountered during the execution phase. Unfortunately, this is rarely the case and the optimal processing is only achieved in a few situations. However, enriching cost models with further parameters increases likelihood and extent of estimate errors, thus, does not guarantee better results in general. In this paper we address the question how to de-couple optimization and execution by transparent means of parallelism, i.e. once the optimizer determined the degree of parallelism for a group of operators, the underlying execution engine ensures optimal parallel execution without demanding any static schedule by the optimizer. Based on an analytical framework we model both dataflow and processing environment for parallel query execution. On this ground we develop the notion of Non-look-ahead Optimality which reflects an execution strategy's ability of ad-hoc resource utilization. We prove a tight upper bound for the processing time of such strategies and show that they are insensitive to skew. Finally, we model several different strategies and present an execution strategy that fulfills the desired optimality criteria. The new algorithm outperforms conventional pipeline execution substantially and is resistant against various kinds of skew as our experiments confirm.

Scalable Distributed Data Structures (SDDSs) provide a self-managing and self-organizing data storage of potentially unbounded size. This stands in contrast to common distribution schemas deployed in conventional distributed DBMS. SDDSs, however, have mostly been used in synthetic scenarios to investigate their properties. In this paper we concentrate on the integration of the LH* SDDS into Monet, our efficient and extensible DBMS. We show that this merge provides high performance processing and scalable storage of very large sets of distributed data. In our implementation we extended the Monet language interpreters operators in such a way that access to data, whether it is distributed or locally stored, is transparent to the user. Performance measures show viability of our approach, querying using a number of operators on distributed data on a number of nodes.

Content-based image retrieval systems rely on a query-by-example technique often using a limited set of global image features. This leads to a rather coarse-grain approach to locate images. The next step is to concentrate on queries over spatial relations amongst objects within the images. This calls for a small collection of image retrieval primitives to form the basis of an image retrieval system. The Acoi algebra is such an extensible framework built on the relational algebra. New primitives can be added readily, including user-defined metric functions for searching. We illustrate the expressive power of the query scheme using a concise functional benchmark for querying image databases.

Algebraic transformation and optimization techniques have been the method of choice in relational query execution, but applying them in object-oriented (OO) DBMSs is difficult due to the complexity of OO query languages. This paper demonstrates that the problem can be simplified by mapping an OO data model to the binary relational model implemented by Monet, a state-of-the-art database kernel. We present a generic mapping scheme to flatten data models and study the case of straightforward OO model. We show how flattening enabled us to implement a query algebra, using only a very limited set of simple operations. The required primitives and query execution strategies are discussed, and their performance is evaluated on the 1-GByte TPC-D (Transaction-processing Performance Council's Benchmark D), showing that our divide-and-conquer approach yields excellent results.

The Acoi project provides a large-scale experimentation platform to facilitate studies in the area of indexing multimedia objects and their subsequent retrieval. The index model is based on assembling the results of feature detection algorithms into hierarchical structures to classify the objects. This paper provides an overview of the Acoi architecture and the Feature Detector Engine (FDE) model. Central to its design is a grammatical description of the feature relations to classify the multimedia objects and to steer their detection and storage. Its role is informally introduced.

Image retrieval systems based on the image-query-by-example paradigm locate their answer set using a similarity measure of the query image with all images stored in the database. Although this approach generally works for quick re-location of `identical' or partly occluded images, it does not support the more interesting query type aimed at finding images with a particular image fragment. In this paper we introduce a regionbased indexing scheme to support retrieval of images on the basis of both global and local image features.

Transformation-based optimizers that explore a search space exhaustively usually apply all possible transformation rules on each alternative, and stop when no new information is produced. In general, different sequences of transformation rules may end up deriving the same element. The optimizer must detect and discard these duplicate elements generated by multiple paths. In this paper we consider two questions: How bad is the overhead of duplicate generation? And then, how can it be avoided? We use a restricted class of join reordering to illustrate the problem. For the first question, our analysis shows that as queries get larger, the number of duplicates is several times that of the new elements. And even for small queries, duplicates are generated more often than new elements. For the second question, we describe a technique to avoid generating duplicates, based on keeping track of (a summary of) the derivation history of each element.

Query optimizers that explore a search space exhaustively using transformation rules usually apply all possible rules on each alternative, and stop when no new information is produced. A memoizing structure was proposed in [McKenna93] to improve the re-use of common subexpression, thus improving the efficiency of the search considerably. However, a question that remained open is, what is the complexity of the transformation-based enumeration process? In particular, with n the number of relations, does it achieve the O(3^n) lower bound established by [OL90]? In this paper we examine the problem of duplicates, in transformation-based enumeration. In general, different sequences of transformation rules may end up deriving the same element, and the optimizer must detect and discard these duplicate elements generated by multiple paths. We show that the usual commutativity/associativity rules for joins generate O(4^n) duplicate operators. We then propose a scheme ---within the generic transformation-based framework--- to avoid the generation of duplicates, which does achieve the O(3^n) lower bound on join enumeration. Our experiments show an improvement of up to a factor of 5 in the optimization of a query with 8 tables, when duplicates are avoided rather than detected.