RoboCup 2005: 机器人足球世界杯的科技盛宴

需积分: 10 57 浏览量更新于2024-07-18 收藏 17.82MB PDF 举报

"RoboCup 2005: Robot Soccer World Cup IX" 是一本关于2005年机器人世界杯足球赛的会议论文集，由Ansgar Bredenfeld、Adam Jacoff、Itsuki Noda和Yasutake Takahashi编辑。这次第九届RoboCup国际研讨会在日本大阪的INTEX大阪举行，紧随其后的是RoboCup的足球、救援和少年比赛。会议吸引了来自全球各地的RoboCup研究者，他们展示了在机器人足球相关领域的科学和技术贡献。提交给研讨会的论文总数达到131篇，经过国际程序委员会的评选，36篇被选为全篇论文，38篇作为海报展示。这些论文来自21个国家，并在6场口头报告会和2场海报展示会中呈现。其中，两篇全篇论文获得了奖项。科学奖授予了Jelle Kok和Nikos Vlassis撰写的关于多智能体决策制定的Max-Plus算法在协调图中的应用的论文。该书属于“人工智能讲义”系列，是“计算机科学讲义”的子系列，由Jaime G. Carbonell和Jörg Siekmann担任系列编辑。具体章节涵盖了多个主题： 1. 奖项论文 - 包括获得科学奖的论文。 2. 全篇论文 - 人类形态机器人相关的研究。 3. 学习、分析、传感器控制 - 讨论机器人学习、系统分析以及传感器控制技术。 4. 定位、设备、工具、其他 - 探讨机器人定位技术、专用设备和工具以及其他相关主题。 5. 多智能体、机器人 - 关注多机器人协作和智能体的研究。 6. 救援 - 介绍机器人在救援任务中的应用。 7. 视觉 - 讨论机器视觉技术和算法。 8. 海报 - 以海报形式展示的其他研究。此书汇集了全球顶尖的RoboCup研究者们的最新成果，不仅反映了机器人足球领域的前沿进展，也展示了人工智能、多智能体协作、机器学习、感知和控制等多个交叉学科的发展。通过这些论文，读者可以深入了解如何利用人工智能技术来解决机器人足球比赛中的实际问题，同时也可以洞见这些技术在更广泛领域的潜在应用。

Table of Contents XVII

Speciﬁcationsand DesignofGraphicalInterface for HierarchicalFinite

State Machines

Vincent Hugel, Guillaume Amouroux, Thomas Costis,

Patrick Bonnin, Pierre Blazevic ................................. 648

Task Allocation forthePolice Force Agents in RoboCupRescue

Simulation

Mohammad Nejad Sedaghat, Leila Pakravan Nejad, Sina Iravanian,

Ehsan Raﬁee .................................................. 656

The Advantages oftheSignaling Strategyina DynamicEnvironment:

Cog

nitive Modeling UsingRoboCup

Sanjay Chandrasekharan, Babak Esfandiari, Tarek Hassan .......... 665

Towards Eliminating Manual ColorCalibration at RoboCup

Mohan Sridharan, Peter Stone ................................... 673

Traction Control foraRocker-BogieRobot with Wheel-Ground

Contact AngleEstimation

Mongkol Thianwiboon, Viboon Sangveraphunsiri ................... 682

Velocity Control o

fan Omnidirectional RoboCup Player with Recurrent

NeuralNetworks

Mohamed Oubbati, Michael Schanz, Thorsten Buchheim,

Paul Levi ..................................................... 691

VeryHigh Speed, Close Field, Object Positioning Using Tri-linear CCDs

David Jahshan ................................................ 702

VisualBased Localization foraLegged Robot

Francisco Mart´ın, Vicente Matell´an, Jose Mar´ıa Ca˜nas,

Pablo Barrera ................................................. 708

VolksBo

t -AFlexibleComponent-Based MobileRobot System

Thomas Wisspeintner, Walter Nowak, Ansgar Bredenfeld ........... 716

Author Index ................................................... 725

Using the Max-Plus Algorithm for Multiagent

Decision Making in Coordination Graphs

JelleR.Kokand Nikos Vlassis

Informatics Institute, University of Amsterdam, The Netherlands

{jellekok, vlassis}@science.uva.nl

Abstract. Coordination graphs oﬀer a tractable framework for coop-

erative multiagent decision making by decomposing the global payoﬀ

function into a sum of local terms. Each agent can in principle select an

optimal individual action based on a variable elimination algorithm per-

formed on this graph. This results in optimal behavior for the group, but

its worst-case time complexity is exponential in the number of agents,

and it can be slow in densely connected graphs. Moreover, variable elim-

ination is not appropriate for real-time systems as it requires that the

complete algorithm terminates before a solution can be reported. In this

paper, we investigate the max-plus algorithm, an instance of the belief

propagation algorithm in Bayesian networks, as an approximate alter-

native to variable elimination. In this method the agents exchange ap-

propriate payoﬀ messages over the coordination graph, and based on

these messages compute their individual actions. We provide empirical

evidence that this method converges to the optimal solution for tree-

structured graphs (as shown by theory), and that it ﬁnds near optimal

solutions in graphs with cycles, while being much faster than variable

elimination.

1 Introduction

A multiagentsystem (MAS) consists ofagroup of agents that interact which

each other [1, 2]. In such systems agents act individually, but the outcome can

diﬀer based on the behavior oftheother agents.Inthispaper,weconcentrate

on cooperative MASs in which the agents try tooptimize a shared performance

measure andhaveto ensure that theirselected individual actionsresult in good

team behavior. RoboCup [3] isagoodexample ofacooperative (orteam)MASin

which the agents also haveto dealwith time constraints since the soccer-playing

robots haveto coordinate theiraction

s in real-time in order towin.

A recently introduced framework formultiagentcoordination istheconcept

ofcoordination graphs (CG)[4], which allowsfor a tractable representation of

the coordination problem.Inthisframework, payoﬀ functionsbetween subsets of

the agents are speciﬁed that represent lo

cal coordination dependencies between

the agents.Inorder to determinetheoptimaljointaction that maximizes the

sum ofthelocal payoﬀs, a variableelimination (VE) algorithm was proposed

in [4]. Weapplied CGs and VEtoour UvA Trilearn RoboCup Simul

ation team,

A. Bredenfeld et al. (Eds.): RoboCup 2005, LNAI 4020, pp. 1–12, 2006.

 Springer-Verlag Berlin Heidelberg 2006

2 J.R. Kok and N. Vlassis

which won the RoboCup-2003 WorldChampionship [5]. However, although VE is

exact andalwaysproduces the optimaljointaction, itcan be slow in certain cases

and in the worst case scales exponentially in the number of agents fordensely

connected graphs.Inprevious work [6], weco

mpared two diﬀerentalternatives to

VE.Inthispaperwe will concentrate further on the max-plus algorithm,which

isanalogous to the belief propagation algorithm [7, 8,9] for Bayesiannetworks,

as an approximate alternativetoVE.Inthismetho

d, the agents repeatedly

exchange payoﬀ messages on which they base their individual action selection.

In thispaper,weprovide empirical evidence that thismethodconverges to the

optimal solution fortree-structured graphs andalso show that itﬁnds near

optimal solutions in densely

connected graphs with cycles,whilebeingmuch

faster thanVE.These results make thisframework interestingfordomainsas

RoboCup where real-time decision making in agroup ofdistributed cooperative

agents is ofgreatimportance.

2 Coordination Graphs and Variable Elimination

In this section we will review the problem ofcomputingacoordinated action for

agroup of n agents usingthevariable elimination (VE) algorithm [4]. Each agent

chooses anindividual action a

fromasetA

, and the resulting joint action a =

,...,a

) generates a payoﬀ u(a) fortheteam.The coordination problem is

to ﬁndtheoptimaljointaction a

∗

that maximizes u(a), i.e., a

∗

= arg max

u(a).

An obvious approach isto enumerate all possible jointactionsandselect the one

that maximizes u(a). However, this approach quickly becomes impractical, since

the jointaction space ×

growsexponentially with the number of agents n.

Fortunately, many problems exhibittheproperty that the payoﬀ matrix u(a)

issparse. Each agent only depends on asmall subset oftheother agents, e.g., in

roboticsoccer only robots that are close to each other haveto coo

rdinate their

actions.Arecent approach to exploitsuchdependencies involves the use ofa

coordination graph [4], which decomposes the global payoﬀ function u(a)into a

linear combination of local payoﬀ functions, each involving only afew agents.For

example, apayoﬀ

function involvingfour agents can be decomposed as follows:

u(a)=f

)+f

). (1)

The functions f

specify the local coordination dependencies between the actions

of the agents andcan be mapped to agraphG =(V, E)inwhich each node in

V represents an agent,whilean edge in E deﬁnes a coordination dependency

between two agents. Only interconnected agents haveto coordin

ate theiractions

at any particular instance.The global coordination problem isthusreplaced by

a number of local coordination problems each involvingfewer agents.

In order to ﬁndtheoptimaljointaction a

∗

wecan apply VE,which is essen-

tially identical tovariableelimination in a Bayesiannetwork [10]. The algorithm

operatesasfollows. One agent isselected andcollects all payoﬀ functions in

which it is involved from its neighbors

.Next,it optimizes its decision condition-

ally on the possibleaction combinations of its neighbors andcommunicates the

Using the Max-Plus Algorithm for Multiagent Decision Making 3

resulting ‘conditional’ payoﬀ function toone of its neighbors.Thereafter, this

agent iseliminated fromthegraph.Whenonlyone agentremains, this agent

selects an action that maximizes the ﬁnal conditional strategy. A secondpassin

the reverse order isthen perf

ormed in which every agentcomputes its optimal

action based on its conditional strategy andtheﬁxed actions of its neighbors.

We will illustrate VE on the aforementioned decomposition (1). Weﬁrstelim-

inate agent 1. This agentdepends on the local payoﬀ function

s f

and f

and

therefore the maximization of u(a)in(1)can be written as

max

u(a)= max



)+max

)+f

)]



. (2)

Agent 1 deﬁnes the function φ

)=max

)+f

)]

andthebest-response (conditional strategy) function B

)=arg max

)+f

)] which respectively return the maximalvalue andthe

associated best action for agent 1 given the actions of agent2and 3. The function

)is independent of agent 1, which cannowbe eliminated fromthe

graph, simplifying (2) to max

u(a)=max

)+φ

)]. Note

that the elimination of agent 1induces a new dependency between agent2and

3 andthusachange in the graph’stopology.

Next,weapply the same procedure to eliminate agent2.Since only φ

de-

pends on agent2,wedeﬁne B

)=arg max

) andreplace φ

by φ

)=max

) producingmax

u(a)=max

)], which is independent of a

.Next,weeliminate agent 3 givingmax

u(a)=max

)with φ

)=max

)+φ

)]. Agent4isthe

last remaining agentandﬁxes its optimal action a

∗

= arg max

). There-

after, asecondpassin the reverse elimination order isperformed in which each

agentcomputes its optimal(unconditional) action from its best-response func-

tion andtheﬁxed actionsfrom its neighbors.Inour example, agent 3 ﬁrst selects

∗

= B

∗

). Similarly, wegeta

∗

= B

∗

) and a

∗

= B

∗

). In the case

that one agenthasmore thanonemaximizingbest-response action, itcan select

onerandomly, since italwayscommunicates its choice toits neighbors.

The outcome of VE is independent oftheelimination order andalwaysre-

sults in the opti

maljointaction. On the other hand, the execution time ofthe

algorithm does depend on the elimination order

and isexponentialinthe in-

duced width of the graph (the size ofthelargest clique computed during node

elimination). Thiscan be slow in certain cases and in the worst case scales expo-

nentially in n.Furthermore,VE will only produce its ﬁnal resultaftertheend of

the secondpass.This i

s notalways appropriate forreal-time multiagentsystems

where decision makingmustbedoneunder time constraints.Forexample,inthe

RoboCup 2DSimulation League, each agenthasto sentan action to the server

within 100ms.Inthese cases, an anytime algorithm that improv

es the qualityof

the solution over time wouldbemore appropriate.

Computing the optimal order for minimizing the runtime costs is known to be NP-

complete, but good heuristics exists, e.g., minimum deﬁciency search which ﬁrst

eliminates the agent with the minimum number of neighbors [11].

4 J.R. Kok and N. Vlassis

)

Fig. 1. Graphical representation of diﬀerent messages μ

in a graph with four agents

3 The Max-Plus Algorithm

In this section, we describe the max-plus algorithm [7, 8,9,6] as an approximate

alternativetoVE.The max-plus algorithm isapopular methodforcomput-

ingthemaximum a posteriori (MAP) conﬁguration in an(unnormalized) undi-

rected graphical model. Thismethod, analogous to the belief propagation (BP)

orsum

-product algorithm in Bayesiannetworks,operates byiteratively sending

messages μ

), which can be regarded as locally optimized payoﬀ functions,

between agent i and j over the edges of the graph.Fortree-structured graphs, the

message updates converge to aﬁxed pointafteraﬁnite number of iterations [7].

Wecan translate the aboveresulttoour multiagentdecision makingproblem,

since computingthe

MAP conﬁguration isequivalentto ﬁndingtheoptimaljoint

action in aCG[6]. Suppose that wehaveacoordination graph G =(V,E)with

|V | vertexes and |E| edges.Instead of variables, the nodes in V represent agents,

whiletheglobal payoﬀ function can be decomp

osed as follows

u(a)=



i∈V



(i,j)∈E

). (3)

Here f

denotes a local payoﬀ function for agent i and is only based on its

individual action a

.Furthermore,(i, j) ∈ E denotes a pair of neighboring agents

(an edge in G), and f

isalocal payoﬀ function that maps two actions (a

)

to arealnumber f

). A function f

thus represents the payoﬀ an agent

contributes to the system whenitactsindividually, e.g., dribbling with the ball,

and f

represents the payoﬀ ofacoordinated action, e.g., acoordinated pass.

Again, the goalisto ﬁndtheoptimaljointaction a

∗

that maximizes (3). Each

agent i (node in G) repeatedly sends a message μ

toits neighbors j ∈ Γ (i),

where μ

maps an action a

of agent j to arealnumber as follows:

)=max



)+f



k∈Γ (i)\j

)



+ c

, (4)

where Γ (i) \ j represents all neighbors of i except j and c

isanormalization

vector.This message can be understoodasan approximation ofthemaximum

Note that this function u(a) is analogous to the log-transform of an (unnormalized)

factorized probability distribution for which the MAP state is sought.

剩余741页未读，继续阅读

Cizar

粉丝: 42
资源: 62

RoboCup 2005: 机器人足球世界杯的科技盛宴

全国机器人大赛RoboCup2013：中国II型探险车源码分享

RobocupRescue:TP项目中图形模拟与机器人路径规划研究

江南大学阿福队RoboCup3D：构建仿真足球队的技术探索

RoboCup 2008- Robot Soccer World Cup XII

robocup17:Talentum团队的RoboCup 2017 CoSpace计划

RobocupRescue:TP 项目 ISI 3 - Robocup Rescue

robocup middle size robot control program

RoboCup 2005 Soccer Simulation 2D Final.mp4

iceberg.18:RoboCup Junior Soccer 2018-“ Iceberg Robots”团队-主要arduino

Robot-Soccer-2013:RoboCup 少年足球机器人分享（CAD、软件、电子、材料和所有东西）

最新资源