9573165
Teaching new teammates
Knowledge transfer between expert and novice agents is a challenging problem given that the knowledge representation and learning algorithms used by the novice learner can be fundamentally different from and inaccessible to the expert trainer. We are particularly interested in team tasks, robotic or otherwise, where new teammates need to replace currently indisposed team member(s). We are interested in a general knowledge transfer framework where existing team members or experts can train a new agent to follow its role in team coordination by using exemplars of desirable behavior. Each such exemplar presents a team situation and a preferred action. We envisage an iterative training process where the trainer selects more exemplars in the next iteration based on the errors made by the learner in action choices for test exemplars presented in the current iteration. Such an iterative, exemplar based generic knowledge transfer scheme can be used by agents using arbitrary knowledge representation and learning methods. We evaluate the success of training new teammates in the well-known pursuit problem, where some of the current set of expert predators is being replaced by new ones with no a priori hunting knowledge. Experimental results demonstrate the robustness of our knowledge transfer scheme with a graceful performance degradation.
43158386
Evolution and learning in multiagent systems
1062630
The Role of Commitment in Cooperative Negotiation
Cooperative information agents need mechanisms that enable them to work together effectively while solving common problems. We investigate the use of commitment by agents to proposed actions as a mechanism that allow agents to work concurrently on interdependent problems. Judicious use of commitment can not only increase the throughput of cooperative information systems, but also allow them to deal flexibly with dynamically changing environments. We use the domain of distributed scheduling to demonstrate that static commitment strategies are ineffective. Results from simulated experiments are used to identify the environmental features on which an adaptive commitment strategy should be predicated.
12119095
Correlating Internal Parameters and External Performance: Learning Soccer Agents
We have developed a Soccer simulator in Java, which allows us to evaluate agent behavioral strategies for effectively collaborating with other team members while countering threats posed by the opposing team. Whereas action selection mechanisms to decide when to shoot, pass, dribble, guard opponent, tackle, etc. are important from a player's viewpoint, learning the capabilities of individual opponents from repeated encounters can provide critical information for the success of a team. Each agent is described by a set of skill levels for different soccer skills. A soccer agent uses its incomplete perceptions, model of the changing environment, knowledge of the skill levels of its own team players, and estimated skill levels of the opponent team players to select the most prudent action. In this paper, we identify learning opportunities for soccer agents, and investigate some of these possibilities in detail. Initial experimental results demonstrate the advantage of learning agents.
3526092
Selecting partners
1. I N T R O D U C T I O N In an open environment the goal of a self-interested agent would be to interact with or enter into partnership with those agents that will produce maximal local utility for this agent [5]. We assume that an agent can get one of several payoffs (utilities) for joining a particular coalition which is determined by a static probability distribution over the payoffs for each coalition. We consider choosing a single coalition to interact with repeatedly when the total number of interactions is known ahead of time.
15974834
Learning Pareto-optimal Solutions in 2x2 Conflict Games
Multiagent learning literature has investigated iterated two-player games to develop mechanisms that allow agents to learn to converge on Nash Equilibrium strategy profiles. Such equilibrium configurations imply that no player has the motivation to unilaterally change its strategy. Often, in general sum games, a higher payoff can be obtained by both players if one chooses not to respond myopically to the other player. By developing mutual trust, agents can avoid immediate best responses that will lead to a Nash Equilibrium with lesser payoff. In this paper we experiment with agents who select actions based on expected utility calculations that incorporate the observed frequencies of the actions of the opponent(s). We augment these stochastically greedy agents with an interesting action revelation strategy that involves strategic declaration of one's commitment to an action to avoid worst-case, pessimistic moves. We argue that in certain situations, such apparently risky action revelation can indeed produce better payoffs than a non-revealing approach. In particular, it is possible to obtain Pareto-optimal Nash Equilibrium outcomes. We improve on the outcome efficiency of a previous algorithm and present results over the set of structurally distinct two-person two-action conflict games where the players' preferences form a total order over the possible outcomes. We also present results on a large number of randomly generated payoff matrices of varying sizes and compare the payoffs of strategically revealing learners to payoffs at Nash equilibrium.
1068367
An Efficient Output-Size Sensitive Parallel Algorithm for Hidden-Surface Removal for Terrains
Abstract. We describe an efficient parallel algorithm for hidden-surface removal for terrain maps. The algorithm runs in O(log 4 n) steps on the CREW PRAM model with a work bound of O((n+k) \polylog ( n)) where n and k are the input and output sizes, respectively. In order to achieve the work bound we use a number of techniques, among which our use of persistent data structures is somewhat novel in the context of parallel algorithms.
9417710
Using real-valued genetic algorithms to evolve rule sets for classification
In this paper, we use a genetic algorithm to evolve a set of classification rules with real-valued attributes. We show how real-valued attribute ranges could be encoded with real-valued genes and present a new uniform method for representing don't cares in the rules. We view supervised classification as an optimization problem, and evolve rule sets that maximize the number of correct classifications of input instances. We use a variant of the Pitt approach to genetic-based machine learning system with a novel conflict resolution mechanism between competing rules within the same rule set. Experimental results demonstrate the effectiveness of our proposed approach on a benchmark wine classifier system.<<ETX>>
16723670
PLEASE: A Prototype Learning System Using Genetic Algorithms
Prototypes have been proposed as representation of concepts that are used eeec-tively by humans. Developing computational schemes for generating prototypes from examples , however, has proved to be a dii-cult problem. We present a novel genetic algorithm based prototype learning system, PLEASE, for constructing appropriate prototypes from classiied training instances. After constructing a set of prototypes for each of the possible classes, the class of a new input instance is determined by the nearest prototype to this instance. Attributes are assumed to be ordinal in nature and prototypes are represented as sets of feature-value pairs. A genetic algorithm is used to evolve the number of prototypes per class and their positions on the input space. We present experimental results on a series of artiicial problems of varying complexity. PLEASE performs competitively with several nearest neighbor clas-siication algorithms on the problem set. An analysis of the strengths and weaknesses of the initial version of our system motivates the need for additional operators. The inclusion of these operators substantially improves the performance of the system on particularly diicult problems.
1922221
Improved Algorithms for Uniform Partitions of Points

AbstractWe consider the following one- and two-dimensional bucketing problems: Given a set S of n points in \reals1 or \reals2 and a positive integer b , distribute the points of S into b equal-size buckets so that the maximum number of points in a bucket is minimized. Suppose at most (n/b) + Δ points lie in each bucket in an optimal solution. We present algorithms whose time complexities depend on b and Δ . No prior knowledge of Δ is necessary for our algorithms.For the one-dimensional problem, we give a deterministic algorithm that achieves a running time of O(b4 (Δ2+log n) + n) . For the two-dimensional problem, we present a Monte Carlo algorithm that runs in subquadratic time for small values of b and Δ . The previous algorithms, by Asano and Tokuyama [1], searched the entire parameterized space and required Ω ( n2 ) time in the worst case even for constant values of b and Δ . We also present a subquadratic algorithm for the special case of the two-dimensional problem when b=2 .

30243464
Planar Graph Blocking for External Searching
We present a new scheme for storing a planar graph in external memory so that any online path can be traversed in an I-O efficient way. Our storage scheme significantly improves the previous results for planar graphs with bounded face size. We also prove an upper bound on I-O efficiency of any storage scheme for well-shaped triangulated meshes. For these meshes, our storage scheme achieves optimal performance.