"> Simulator Gallery

Simulator Gallery

     We developed an initial version of the free market architecture and tested it in a distributed sensing problem in several simulated interior environments. A group of robots, located at different starting positions in known simulated worlds, were assigned the task of visiting a set of pre-selected observation points. This problem is equivalent to the distributed traveling salesman problem, where the observation points are the cities to visit. Each robot was equipped with a map of the world, which enabled it to calculate the cost associated with visiting each of these cities. The costs were the lengths of the shortest paths between cities in an eight-connected grid, interpreted as money. Thus, the robots bid for each city based on their estimated costs to visit that city.
     The interface between the human operator and the team of robots was a software agent, the operator executive (exec). The exec conveyed the operator's commands to the members of the team, managed the team revenue, monitored the team cost, and carried out the initial city assignments. Being a self-interested agent, the exec aimed to assign cities quickly while minimizing revenue flow to the team. In our initial implementation, the exec adopted a greedy algorithm for assigning tasks.
     Once the exec had completed the initial city assignments, the robots negotiated amongst themselves to subcontract city assignments. Each of the robots, in turn (the initial implementation was fully synchronous), offered all the cities on its tour (individually) to all the other robots for a maximum price equal to the offerer's cost reduction by removing that city from its tour. Each bidder then submitted a bid for that city greater than the cost for adding the city to its tour. In this initial implementation, only single-city deals were considered, and the robots continued to negotiate amongst themselves until no new, mutually profitable deals were possible. Thus, negotiations ceased once the system settled into a local minimum of the global cost.
     The worlds shown below are a sample of the worlds we use to run test simulations. If you click on the floorplan of Worlds 1 through 4 you can view a simulator movie run in that world and read a description explaining the movie. If you click on the FRC World floorplan you will be taken to a listing of movies, each illustrating different scenarios. The FRC World simulations are important because they give us an idea of what will happen when we run our test bed robots in the FRC.


World 1

World 2

World 3

World 4

FRC World