Embedded Files
Complex problems in nature are solved by organizing independent life units (agents) into societies, where each agent is capable of autonomous decision making. The problems that multi-agent systems can solve are most likely impossible for a monolithic system or a single agent. For example, the white blood cells coordinate to fight pathogens, ants cooperate to find food, the competition between predators and prey maintains a delicate ecological balance. We first look at agent based modeling and simulation to solve problems like finding shortest path, lattice formation. We then discuss a fail stop distributed auction design and finally, present a mechanism design for auctions when items themselves are autonomous agents. Following is the list of projects in this page,
Finding the Shortest Path Using Ant Colony Optimization
This project was done at IIIT-B during Fall 2009 under the guidance of Prof. G.N.S Prasanna.
The project aims to find the shortest path between two objects in the presence of obstacles when the coordinates one of the objects is unknown. We solve this by simulating the behavior of Ants in finding food. When an ant returns to its colony after finding food, it lays down a trail of chemical called pheromone along its path which attracts other ants to follow the trail. The pheromone evaporates over time and eventually, the trails along all paths except the shortest path (may not be the global minimum) evaporates. This causes almost all ants to follow the current shortest path until another ant found an even shorter path (by wandering randomly). The simulation reports the length of the shortest path found after a fixed number of iterations. Our results show the error to be less than one percent of the optimal solution with a reasonable number of iterations.
Downloads: Source Code
Our implementation provides several tunable parameters that give the simulation a finer control. These parameters can be modified in the source file: arun/aco/GlobalSettings.java. Following table lists some of the parameters and their description.
In our simulation, the GUI displays ants as black dots, food as blue rectangular block, pheromone trails change their color as it evaporates, where red trails imply highest intensity which fades away as it evaporates. Obstacles are shown as green rectangular block. The number of ants, location of food and the obstacles are configurable in the source code.
Decentralized Pairing in Multi Agent Systems
This work was done at IIIT-B during fall 2010 as part of the ‘Multi Agent Systems’ class under the guidance of Prof. Srinath Srinivasa.
Problem Statement: Given two types of agents – red and green, located randomly on an n X n grid, our goal is to design optimal strategies for movement of agents such that no two agents of same color are adjacent to each other at equilibrium. Note, these agents only have local knowledge, i.e., they can only determine their immediate neighbors. Note, these agents only have local knowledge, i.e., they can only determine their immediate neighbors. We use Netlogo 4.1 to implement our solution, and as per Netlogo conventions all agents are called as turtles. We formulate the problem statement as a game with the following specification. On an n x n grid, create k turtles of red color and k turtles of blue color at random positions. The turtles come with an initial energy e0. The objective of the turtles is to pair themselves with a turtle of the other color. A turtle loses one unit of energy on every step it takes. Furthermore, at every time step, a turtle loses one unit of energy for every turtle of the same color that exists in the eight neighboring cells. Once a turtle’s energy reaches zero, it is removed from the grid. The system objective is to maximize the overall energy (sum of individual turtle energies) at equilibrium (when no two turtles of same color are adjacent). Once all turtles have been paired, print the overall energy (sum of individual turtle energies) in the system.
Downloads: Project Report Source Code Source Code [script only] Screenshot
Strategy: Our core idea is that each turtle determines its strategy based on the strategy of all other turtles. We associate a two tuple variable called ‘risk’ to each of the patches. The two tuples in the risk variable are, a red_risk value which indicates the number of red turtles surrounding the patch. The other is the green_risk value which indicates the number of green turtles surrounding the patch. The following figure, shows a sample configuration and scores for two of the patches.
Each turtle selects one of the eight neighboring patches with the risk value (of same color) less than its current patch, which is its best response function. For eg: A red turtle will select the neighbor patch which has the lowest red_risk value less than the red_risk value of its own patch. If it finds a neighbor patch with this criteria, then it decides to move to that patch, else it decides to stay where it is. Now, the trick here is that the turtles actually don’t move, they just specify their intent to all neighboring turtles. The details of the data structures are described in section 4. In this way, all turtles now know about the strategy of all other turtles. Now each turtle re-computes its best response function based on the response of all other turtles. For the sake of simplicity we have modeled the belief function of each turtle to believe that that all other turtles will stick to their initial intent. The turtle might now find a different neighboring patch or decide not to move at all. This property of a turtle to not stick to its initial intent is called Defection. And each turtle has a probability with which it can defect which is called "Probability_To_Defect" in our model. where a turtle finds that the risk value of all neighboring patches is greater than or equal to its current value. Hence selecting any of the neighboring patches is clearly irrational. But, if the turtle remains in the same patch and say other turtles also don't move, then it will lose energy and die eventually. So, the turtle has to make an irrational choice at some point, to find low risk patches far beyond. We define the minimum number of rounds before which a turtle makes an irrational decision as the 'Degree_Of_Rationality' in our model.
Fail-Stop Distributed Combinatorial Auctioning Systems With Fair Resource Allocation
This project was done at IIIT-B during spring 2011 under the guidance of Prof. Shrisha Rao.
Project Abstract: A Distributed Combinatorial Auctioning System (DCAS) is a multi-agent system (MAS) where each auctioneer has a set of local bidders and all of them adopt a cooperative strategy in conducting the auction. Any occurrence of failure in the system leads to an unpredictable behavior and hence forcing abandonment of the auction. We systematically analyze the failures occurring in the agents and propose a fail-stop design of the DCAS. We present a set of Event Based Failure Handlers (EBFHs) that are triggered upon receiving specific messages from other agents in the network. We provide a proof of correctness of our approach and analyze the efficiency in terms of the message complexity. We also discuss the different parameters that influence the performance of a given DCAS configuration. We use the framework in which the concepts of basic and extended fairness are used in the bidding process.
Publication:
A. Kalyanasundaram, R. A. K. Lalkhanwar, and S. Rao, “Fail-Stop Distributed Combinatorial Auctioning Systems with fair resource allocation,” in 7th Annual IEEE Conference on Automation Science and Engineering (IEEE CASE 2011), Trieste, Italy, Aug. 2011, pp.181–188, doi:10.1109/CASE.2011.6042428. [Download]
Downloads: Full Paper PPT Abstract Slide Source code (simulation)
Strategies for Collision Avoidance in Multi-Agent Systems
This work was done at IIIT-B during fall 2010 as part of the ‘Multi Agent Systems’ class under the guidance of Prof. Srinath Srinivasa.
Problem Statement: Given a set of agents located randomly in an n X n grid, our goal is to move these agents in discrete steps of [-1, +1] either in the horizontal and/or vertical direction without colliding with each other. Collisions occur when two or more agents are on the same grid at the same time step. In the event of collision, the colliding agents become immobile and turn into an obstacle.
Downloads: Project Report Source Code Source Code [script only] Screenshot
We design and implement four different strategies to address this problem. In our approach, we use a deterministic model where each turtle moves in discrete steps of one in x, y directions. We assign a “score” to each of the neighboring empty patch and the turtle picks the one with the lowest score as its next hop. The knowledge each turtle has determines how effectively they compute the score. We have analyzed the algorithm for three different levels of turtle intelligence, one is that the turtles only know about their own patch, second the turtles know about their neighbors and third they also know about their neighbor’s neighbors. Finally, we look at the behavior when each turtle has a preferred direction.
Items as Autonomous Agents in Combinatorial Auctions
This work was done at IIIT-B during fall 2010 as part of the ‘Multi Agent Systems’ class under the guidance of Prof. Srinath Srinivasa.
Project Abstract: Auctions in general involve strategies adopted by the bidders and the auctioneer(s) in order to maximize their payoffs on a set of items. But our focus is on the type of auctions where the items themselves are autonomous agents, like the Indian Premier League (IPL) auctions. The IPL auctions are conducted in a typical English auction setting where bids are placed on individual players (items). A major drawback is that it does not capture the preferences of the players which is a key to their performance. We propose a mechanism which models the agents (players and bidders) as autonomous decision making agents driven by their self interest and preferences. We later show that this benefits both the players and the bidders since it takes into account their intrinsic payoffs. We introduce a ‘two part’ round structure where the first part involves placing bids by the bidders and the second part involves a voting operation performed by the players. We also introduce a combinatorial auction setting where the players are divided into a finite number of ‘groups’. The effectiveness of the design is discussed based on certain fairness criterion and adversarial arguments. The system is studied using a simulation framework to analyze the equilibrium conditions, group formation techniques and to monitor parameters like happiness score, bidder expenditure, etc.
Downloads: Report Source Code Source Code [script only] Presentation Proposal
Page updated
Google Sites
Report abuse