Coordinating Specialized Robots with a Market-based ApproachGabe Reinstein and Austin WangDecember 10, 2002IntroductionBackground: The Market-Based ApproachMotivation: What was missing from the previous researchHypothesisExperimentOverviewSimulationCost FunctionSpecializationImplementation OverviewSimulationBoardBoard ObjectsTreasureRobotsThe Robot class (and its subclasses, Scout and Hauler) represents the robots on the board. It is responsible for maintaining the state of each robot and performing its actions in the game. Each robot has a “currentTask” that keeps track of its state in the game, a field for holding treasure (which is null when the robot has no treasure), and a set of attributes: “sensingRange,” the radius of squares around the robot in which it can sense treasure; “unladenMoveProbability,” which determines the robot’s speed when it is not holding anything; and “ladenMoveProbability,” which determines the robot’s speed when it is carrying treasure. These attributes are the only differences between scouts and haulers, and so the Scout and Hauler classes merely fill in these values so that the robots can be instantiated.Movement is handled probabilistically. The board grid and the time scale are discrete, and robots can only move one square at a time (horizontally or vertically), but they need to have different relative speeds. So, on any turn, a robot “rolls the dice” to determine whether or not it can move by a square. Over time, robots with higher movement probabilities will move faster (at least, they will tend to move farther in a given number of turns). Scouts have a higher unladenMoveProbability than haulers, but haulers have a higher ladenMoveProbability than scouts—therefore, scouts are faster explorers, but haulers are faster when carrying treasure.The most important method in the Robot class is takeTurn(), which is called for each robot on every turn of the game and performs one time-step worth of actions. The action carried out in takeTurn() depends on the “currentTask” of the robot. If the robot is heading towards a treasure (“harvest” task), it tries to move in the direction of the treasure or picks the treasure up. If it is heading towards base with a treasure in hand (“return” task), it tries to move in the direction of the base, or drops the treasure off if it has reached the base. Otherwise, if it is in the “explore” state, the robot first tries to make a move. It moves in whatever is its “currentDirection,” and changes this direction randomly with some (small) probability. This ensures that robots will tend to move in random directions but won’t keep oscillating back and forth in a small area. After this potential move (governed by the fact that moves only happen with some probability), the robot performs a sensing operation. If it doesn’t find anything, it waits until the next turn. If it does find a treasure, it calls an auction.ResultsDiscussionContributionsReferences6.834J Final Project ReportCoordinating Specialized Robots with aMarket-based ApproachGabe Reinstein and Austin WangDecember 10, 2002INTRODUCTION..........................................................................................................................................2Background: The Market-Based Approach............................................................................................2MOTIVATION: WHAT WAS MISSING FROM THE PREVIOUS RESEARCH...........................................................3Hypothesis..............................................................................................................................................3EXPERIMENT...............................................................................................................................................4OVERVIEW....................................................................................................................................................4IMPLEMENTATION OVERVIEW......................................................................................................................6Simulation...............................................................................................................................................6Board......................................................................................................................................................7Board Objects.........................................................................................................................................7Robots.....................................................................................................................................................7RESULTS........................................................................................................................................................816.834J Final Project ReportDISCUSSION................................................................................................................................................10CONTRIBUTIONS......................................................................................................................................11References......................................................................................................................................................1226.834J Final Project ReportIntroductionThis paper describes an experiment we performed to evaluate the nature of specialization in a multi-robot coordination task governed by a market-based architecture. First we will discuss the background and motivation for the experiment; then, we will explain our experimental hypothesis; next, we will describe the experiment; and finally, we will present our results and discuss them.Background: The Market-Based ApproachThere are many situations in which it is important to coordinate multiple robots. Players on a robot soccer team must work together; a set of agricultural robots need to communicate with each other so that all the land is watered or harvested correctly; and a team of planetary rovers should coordinate so that they don’t all explore the same territory.There are a number of different approaches to coordinating multiple robots. One set of methods uses centralized planning to coordinate the robots. All the robots communicate sensor data to the central “leader,” who calculates an optimal plan and sends commands
View Full Document