Multi-Robot Coordination Using a Market-based ApproachOutlineSource PapersWhy Multiple Robots?A Few Multi-robot ScenariosSlide 6A Good Multi-robot System Is:Slide 8Basic ApproachesCentralized ApproachesCentralized Methods: ProsCentralized Methods: ConsDistributed ApproachesDistributed Methods: ProsDistributed Methods: ConsSlide 16Market-based Approach: The Basic IdeaAnalogy To Real EconomyThe Market Mechanism In Detail: BackgroundHow Do We Determine Profit?ExamplesPrices and BiddingNo CommunicationSubcontracting a TaskHow Are Prices Determined?Competition vs. CoordinationLeadersWhy Is This Good?Slide 29Multi-Robot ExplorationPrevious WorkArchitecture of the Market ApproachExample WorldExploration AlgorithmSlide 35Bidding ExampleExpected vs. RealGoal Selection StrategiesBenefit of PricesInformation SharingExperimental SetupSlide 42Experimental ResultsSlide 44Slide 45ConclusionMulti-Robot Coordination Using a Market-based ApproachGabe Reinstein and Austin Wang6.834JNovember 6, 2002OutlineWhy multiple robots?Design requirementsOther approachesThe market-based approachExample: Multi-robot explorationSource PapersDias, M. B. and Stentz, A. 2001. A Market Approach to Multirobot Coordination. Technical Report, CMU-RI-TR-01-26, Robotics Institute, Carnegie Mellon University.Explains idea of market-based approachZlot, R. et al. 2002. Multi-Robot Exploration Controlled by a Market Economy. IEEE.Describes a particular implementation of this idea: mapping and exploration with multiple robotsWhy Multiple Robots?Some tasks require a teamRobotic soccerSome tasks can be decomposed and divided for efficiencyMapping a large areaMany specialists preferable to one generalistIncrease robustness with redundancyTeams of robots allow for more varied and creative solutionsA Few Multi-robot ScenariosAutomated warehouse managementPlanetary exploration and colonizationAutomatic constructionRobotic cleanup of hazardous sitesAgricultureOutlineWhy multiple robots?Design requirementsOther approachesThe market-based approachExample: Multi-robot explorationA Good Multi-robot System Is:Robust: no single point of failureOptimized, even under dynamic conditionsQuick to respond to changesAble to deal with imperfect communicationAble to allocate limited resourcesHeterogeneous and able to make use of different robot skillsOutlineWhy multiple robots?Design requirementsOther approachesThe market-based approachExample: Multi-robot explorationBasic ApproachesCentralizedAttempting optimal plansDistributedEvery man for himselfMarket-basedCentralized ApproachesRobot team treated as a single “system” with many degrees of freedomA single robot or computer is the “leader”Leader plans optimal actions for groupGroup members send information to leader and carry out actionsCentralized Methods: ProsLeader can take all relevant information into accountIn theory, coordination can be perfect:Optimal plans possible!Centralized Methods: ConsComputationally hardIntractable for more than a few robotsMakes unrealistic assumptions:All relevant info can be transmitted to leaderThis info doesn’t change during plan constructionResult: response sluggish or inaccurateVulnerable to malfunction of leaderHeavy communication loadDistributed ApproachesPlanning responsibility spread over teamEach robot basically independentRobots use locally observable information to make their plansDistributed Methods: ProsFast response to dynamic conditionsLittle or no communication requiredLittle computation requiredSmooth response to environmental changesVery robustNo single point of failureDistributed Methods: ConsNot all problems can be decomposed wellPlans based only on local informationResult: solutions are often highly sub-optimalOutlineWhy multiple robots?Design requirementsOther approachesThe market-based approachExample: Multi-robot explorationMarket-based Approach:The Basic IdeaBased on the economic model of a free marketEach robot seeks to maximize individual “profit”Robots can negotiate and bid for tasksIndividual profit helps the common goodDecisions are made locally but effects approach optimalityPreserves advantages of distributed approachAnalogy To Real EconomyRobots must be self-interestedSometimes robots cooperate, sometimes they competeIndividuals reap benefits of their good decisions, suffer consequences of bad onesJust like a real market economy, the result is global efficiencyThe Market Mechanism In Detail: BackgroundConsider:A team of robots assembled to perform a particular set of tasksEach robot is a self-interested agentThe team of robots is an economyThe goal is to complete the tasks while minimizing overall costsHow Do We Determine Profit?Profit = Revenue – CostTeam revenue is sum of individual revenues, and team cost is sum of individual costsCosts and revenues set up per applicationMaximizing individual profits must move team towards globally optimal solutionRobots that produce well at low cost receive a larger share of the overall profitExamplesCost functions may be complexBased on distance traveledBased on time takenSome function of fuel expended, CPU cycles, etc.Revenue based on completion of tasksReaching a goal locationMoving an objectEtc.Prices and BiddingRobots can receive revenue from other robots in exchange for goods or servicesExample: haulage robotIf robots can produce more profit together than apart, they should deal with each otherIf one is good at finding objects and another is good at transporting them, they can both gainNo CommunicationSubcontracting a TaskHow Are Prices Determined?BiddingRobots negotiate until price is mutually beneficialNote: this moves global solution towards optimumRobots can negotiate several deals at onceDeals can potentially be multi-partyPrices determined by supply and demandExample: If there are a lot of haulers, they won’t be able to command a high priceThis helps distribute robots among “occupations”Competition vs. CoordinationComplementary robots will cooperateA grasper and a transporter could offer a combined “pick up and place” serviceSimilar robots will competeThis drives prices downThis isn’t always
View Full Document
Unlocking...