cmunited-99-sim.ps

1999年卡耐基梅陇大学的2D仿真源代码

D80FC49038F101FC9039C803F20001D801FE7F01D05BA201E05BB03CFFFE3FFF8FFFE0A3
331B7D9A38>I<38FFC07E9038C1FF809038C30FC0D80FC413E0EBC80701D813F013D0A2
13E0B039FFFE3FFFA3201B7D9A25>I<EB3FE03801FFFC3803F07E390FC01F80391F800F
C0393F0007E0A2007EEB03F0A300FE14F8A8007E14F0A26CEB07E0A2391F800FC0390FC0
1F803907F07F003801FFFC38003FE01D1B7E9A22>I<38FFE1FE9038EFFF809038FE0FE0
390FF803F09038F001F801E013FC140015FEA2157FA8157E15FEA215FC140101F013F890
38F807F09038FC0FE09038EFFF809038E1FC0001E0C7FCA9EAFFFEA320277E9A25>I<38
FFC1F0EBC7FCEBC63E380FCC7F13D813D0A2EBF03EEBE000B0B5FCA3181B7F9A1B>114
D<13E0A41201A31203A21207120F381FFFE0B5FCA2380FE000AD1470A73807F0E0000313
C03801FF8038007F0014267FA51A>116 D<39FFE07FF0A3000F1307B2140FA200071317
3903F067FF3801FFC738007F87201B7D9A25>I E end
%%EndProlog
%%BeginSetup
%%Feature: *Resolution 300dpi
TeXDict begin

%%EndSetup
%%Page: 1 1
1 0 bop 304 224 a Fu(The)22 b(CMUnited-99)g(Champion)h(Sim)n(ulator)i
(T)-6 b(eam)521 369 y Ft(P)o(eter)15 b(Stone)732 354
y Fs(1)751 369 y Ft(,)f(P)o(atric)o(k)g(Riley)1017 354
y Fs(2)1034 369 y Ft(,)g(and)f(Man)o(uela)h(V)m(eloso)1425
354 y Fs(2)377 439 y Fr(1)394 455 y Fq(A)m(T&T)e(Labs)h(|)h(Researc)o
(h)1104 439 y Fr(2)1121 455 y Fq(Computer)f(Science)i(Departmen)o(t)370
501 y(180)e(P)o(ark)h(Av)o(e.,)e(ro)q(om)h(A273)324 b(Carnegie)14
b(Mellon)h(Univ)o(ersit)o(y)386 546 y(Florham)f(P)o(ark,)f(NJ)g(07932)
388 b(Pittsburgh,)14 b(P)m(A)f(15213)387 592 y(pstone@researc)o
(h.att.com)367 b Fp(f)p Fq(pfr,v)o(eloso)p Fp(g)p Fq(@cs.cm)o(u.edu)276
638 y(h)o(ttp://www.researc)o(h.att.com/~pstone)142 b(h)o
(ttp://www.cs.cm)o(u.edu/)p Fp(f)p Fq(~pfr,~mm)o(v)p
Fp(g)380 760 y Fo(Abstract.)22 b Fq(The)8 b(CMUnited-99)i(sim)o(ulator)
h(team)e(b)q(ecame)g(the)g(1999)g(Rob)q(oCup)380 805
y(sim)o(ulator)14 b(league)g(c)o(hampion)h(b)o(y)e(winning)i(all)f(8)f
(of)f(its)i(games,)e(outscoring)j(op-)380 851 y(p)q(onen)o(ts)j(b)o(y)f
(a)g(com)o(bined)i(score)e(of)g(110{0.)h(CMUnited-99)g(builds)h(up)q
(on)f(the)380 897 y(successful)g(CMUnited-98)f(implemen)o(tation)q(,)i
(but)d(also)i(impro)o(v)o(es)g(up)q(on)f(it)g(in)380
942 y(man)o(y)e(w)o(a)o(ys.)f(This)h(pap)q(er)g(giv)o(es)h(a)e
(detailed)j(presen)o(tation)f(of)e(CMUnited-99's)380
988 y(impro)o(v)o(emen)o(ts)g(o)o(v)o(er)g(CMUnited-98.)262
1126 y Fn(1)56 b(In)n(tro)r(duction)262 1230 y Ft(The)17
b(CMUnited)g(rob)q(otic)g(so)q(ccer)i(pro)r(ject)f(is)f(an)f(ongoing)g
(e\013ort)h(concerned)i(with)e(the)262 1280 y(creation)10
b(of)g(collab)q(orativ)o(e)f(and)h(adv)o(ersarial)g(in)o(telligen)o(t)f
(agen)o(ts)i(op)q(erating)f(in)g(real-time,)262 1330
y(dynamic)f(en)o(vironmen)o(ts.)i(CMUnited)h(teams)e(ha)o(v)o(e)i(b)q
(een)g(activ)o(e)g(and)f(successful)i(partic-)262 1380
y(ipan)o(ts)i(in)g(the)h(in)o(ternational)e(Rob)q(oCup)h(\(rob)q(ot)g
(so)q(ccer)i(w)o(orld)e(cup\))h(comp)q(etitions)f([1,)262
1429 y(2,)6 b(15].)11 b(In)h(particular,)g(the)h(CMUnited-97)f(sim)o
(ulator)f(team)g(made)g(it)h(to)h(the)g(semi-\014nals)262
1479 y(of)h(the)i(\014rst)f(Rob)q(oCup)g(comp)q(etition)e(in)i(Nago)o
(y)o(a,)e(Japan)i([9],)f(the)h(CMUnited-98)g(sim-)262
1529 y(ulator)i(team)h(w)o(on)g(the)h(second)g(Rob)q(oCup)f(comp)q
(etition)f(in)h(P)o(aris,)g(F)m(rance)h([13],)e(and)262
1579 y(the)d(latest)f(CMUnited-99)h(sim)o(ulator)d(team)h(w)o(on)h(the)
h(third)g(Rob)q(oCup)f(comp)q(etition)f(in)262 1629 y(Sto)q(c)o(kholm,)
f(Sw)o(eden)611 1614 y Fs(1)631 1629 y Ft(.)324 1679
y(The)k(CMUnited-99)f(sim)o(ulator)e(team)h(is)h(mo)q(deled)g(closely)g
(after)h(its)f(t)o(w)o(o)g(predeces-)262 1729 y(sors.)i(Lik)o(e)h
(CMUnited-97)f(and)h(CMUnited-98,)f(it)g(uses)i(la)o(y)o(ered)f
(learning)f([12])f(and)i(a)262 1779 y(\015exible)c(team)f(structure)k
([11].)11 b(In)j(addition,)e(man)o(y)f(of)i(the)h(CMUnited-99)f(agen)o
(t)h(skills,)262 1829 y(suc)o(h)c(as)g(goaltending,)f(dribbling,)f(kic)
o(king,)h(and)h(defending,)f(are)i(closely)f(based)h(up)q(on)f(the)262
1879 y(CMUnited-98)h(agen)o(t)i(skills.)e(Ho)o(w)o(ev)o(er,)h
(CMUnited-99)g(impro)o(v)o(es)e(up)q(on)j(CMUnited-98)262
1928 y(in)e(man)o(y)g(w)o(a)o(ys.)g(This)h(pap)q(er)h(fo)q(cuses)g(on)f
(the)h(researc)o(h)h(inno)o(v)n(ations)c(that)j(con)o(tribute)g(to)262
1978 y(CMUnited-99)o('s)h(impro)o(v)o(emen)o(ts.)324
2029 y(Coupled)d(with)f(the)i(publicly-a)o(v)n(aila)o(ble)c
(CMUnited-99)j(source)h(co)q(de)g([8],)d(this)i(article)262
2079 y(is)k(designed)i(to)f(help)g(researc)o(hers)j(in)o(v)o(olv)o(ed)c
(in)h(the)g(Rob)q(oCup)g(soft)o(w)o(are)g(c)o(hallenge)g([3])262
2129 y(build)g(up)q(on)h(our)h(success.)h(Throughout)e(the)h(article,)f
(w)o(e)h(assume)f(that)g(the)h(reader)h(is)262 2178 y(famili)o(ar)9
b(with)i(the)h(Rob)q(oCup)f(sim)o(ulator,)e(or)j(\\so)q(ccer)h(serv)o
(er")g([5].)d(A)i(detailed)g(o)o(v)o(erview)262 2228
y(of)d(the)i(so)q(ccer)h(serv)o(er,)f(including)e(agen)o(t)h(p)q
(erception)i(and)e(actuator)g(capabilities,)f(is)h(giv)o(en)262
2278 y(in)j([7].)324 2329 y(The)d(pap)q(er)f(b)q(egins)h(b)o(y)f
(brie\015y)h(summarizing)c(the)k(main)d(features)j(of)f(the)h
(CMUnited-98)262 2379 y(sim)o(ulator)d(team)h(\(Section)i(2\).)e
(Section)i(3)f(describ)q(es)i(the)f(impro)o(v)o(emen)o(ts)d(in)i
(CMUnited-99's)p 262 2419 237 2 v 273 2446 a Fr(1)303
2462 y Fq(The)k(CMUnited)h(small-rob)q(ot)h(team)e(is)g(also)h(a)f(t)o
(w)o(o-time)g(Rob)q(oCup)i(c)o(hampion)g([14,)6 b(16].)p
eop
%%Page: 2 2
2 1 bop 262 224 a Ft(lo)o(w-lev)o(el)12 b(skills,)g(including)h(the)i
(in)o(tro)q(duction)e(of)g(teammate)f(and)h(opp)q(onen)o(t)i(mo)q
(deling)262 274 y(capabilities.)f(Section)i(4)f(presen)o(ts)i(the)g
(impro)o(v)o(em)o(en)o(ts)d(in)h(CMUnited-99's)g(team-lev)o(el)262
324 y(co)q(ordination)g(metho)q(ds.)g(Section)h(5)g(fo)q(cuses)h(on)e
(the)i(pro)q(cess)h(b)o(y)d(whic)o(h)h(the)h(lo)o(w-lev)o(el)262
374 y(skills)j(w)o(ere)i(impro)o(v)o(ed.)c(Section)k(6)e(in)o(tro)q
(duces)i(the)g(concept)g(of)f(la)o(y)o(ered)g(extrosp)q(ec-)262
423 y(tion,)e(a)i(k)o(ey)f(adv)n(ance)h(in)f(our)h(dev)o(elopmen)o(t)f
(metho)q(dology)m(.)e(Section)j(7)f(summarizes)262 473
y(CMUnited-99)o('s)14 b(successful)i(p)q(erformance)d(at)h(Rob)q
(oCup-99)f(and)g(concludes.)262 605 y Fn(2)56 b(Bac)n(kground)262
704 y Ft(This)19 b(section)h(summarizes)d(the)j(features)h(of)e(the)h
(CMUnited-97)f(and)g(CMUnited-98)262 754 y(teams)10 b(whic)o(h)h(ha)o
(v)o(e)g(b)q(een)i(carried)f(o)o(v)o(er)f(in)o(to)f(the)i(CMUnited-99)f
(implemen)o(tation.)c(Sub-)262 804 y(sequen)o(t)15 b(sections)g
(emphasize)e(the)i(researc)o(h)g(inno)o(v)n(ations)e(unique)h(to)f
(CMUnited-99.)262 928 y Fm(2.1)47 b(Main)15 b(Lo)q(op)262
1010 y Ft(CMUnited)10 b(agen)o(ts)h(are)g(capable)g(of)f(p)q
(erception,)i(cognition,)d(and)h(action.)g(By)h(p)q(erceiving)262
1060 y(the)i(w)o(orld,)e(they)j(build)e(a)g(mo)q(del)f(of)h(its)h
(curren)o(t)h(state.)f(Then,)g(based)g(on)g(a)f(complex)f(set)262
1110 y(of)i(b)q(eha)o(viors,)g(they)i(c)o(ho)q(ose)f(an)g(action)g
(appropriate)g(for)f(the)i(curren)o(t)g(w)o(orld)e(state.)324
1160 y(A)i(driving)g(factor)g(in)h(the)g(design)f(of)g(the)h(agen)o(t)g
(arc)o(hitecture)h(is)f(the)g(fact)f(that)h(the)262 1210
y(sim)o(ulator)g(op)q(erates)k(in)f(100msec)f(cycles.)h(The)h(sim)o
(ulator)c(accepts)21 b(commands)16 b(from)262 1260 y(clien)o(ts)g
(throughout)g(a)f(cycle)i(and)f(then)g(up)q(dates)h(the)g(w)o(orld)e
(state)i(all)e(at)g(once)i(at)f(the)262 1309 y(end)11
b(of)g(the)g(cycle.)g(Only)g(one)g(action)g(command)d(\(dash,)j(kic)o
(k,)g(or)g(turn\))g(is)g(executed)i(for)e(a)262 1359
y(giv)o(en)i(clien)o(t)g(during)h(a)f(giv)o(en)g(cycle.)h(Mean)o
(while,)f(p)q(erceptions)j(arriv)o(e)d(async)o(hronously)262
1409 y(and)h(unpredictably:)g(agen)o(ts)g(can)h(receiv)o(e)g(an)o
(ywhere)g(from)e(zero)i(to)f(six)g(p)q(erceptions)i(in)262
1459 y(a)d(giv)o(en)h(cycle.)324 1509 y(Therefore,)c(CMUnited)h(agen)o
(ts)f(store)h(p)q(erceptions)g(as)f(they)h(arriv)o(e)f(and)f(then)i(up)
q(date)262 1558 y(their)18 b(in)o(ternal)f(state)i(from)d(these)j
(stored)g(p)q(erceptions)g(and)f(the)g(predicted)h(e\013ects)h(of)262
1608 y(past)12 b(actions)h(only)e(when)i(it)g(is)f(time)f(to)h(tak)o(e)
h(an)f(action.)g(A)g(detailed)h(description)g(of)f(the)262
1658 y(agen)o(ts')h(w)o(orld)h(mo)q(del)e(and)i(ho)o(w)f(it)h(is)f(up)q
(dated)i(is)f(giv)o(en)f(in)h([13].)262 1782 y Fm(2.2)47
b(Agen)o(t)15 b(Skills)262 1864 y Ft(Once)d(the)g(clien)o(t)f(has)h
(determined)f(the)h(serv)o(er's)h(w)o(orld)e(state)h(as)f(accurately)h
(as)g(p)q(ossible,)262 1914 y(it)d(can)h(c)o(ho)q(ose)g(and)g(send)g
(an)f(action)h(to)f(b)q(e)h(executed.)i(It)d(can)h(c)o(ho)q(ose)h(from)
c(among)h(sev)o(eral)262 1964 y(lo)o(w-lev)o(el)k(skills)i(whic)o(h)g
(pro)o(vide)g(it)g(with)g(basic)g(capabilities.)f(The)h(output)h(of)e
(the)i(skills)262 2014 y(are)d(primitiv)o(e)f(mo)o(v)o(emen)o(t)f
(commands.)f(Examples)j(of)g(lo)o(w-lev)o(el)f(skills)g(include)i(kic)o
(king,)262 2064 y(dribbling,)7 b(ball-in)o(terception,)i(goaltending,)f
(defending,)h(and)g(clearing.)g(CMUnited-98's)262 2113
y(v)o(ersions)15 b(of)g(these)h(skills)f(are)g(describ)q(ed)i(in)e
(detail)g(in)f([13].)g(Except)i(where)g(sp)q(eci\014cally)262
2163 y(noted)e(in)f(subsequen)o(t)j(sections,)e(CMUnited-99's)g(lo)o
(w-lev)o(el)e(skills)h(are)i(the)f(same.)324 2213 y(The)f(common)e
(thread)i(among)e(these)k(skills)d(is)h(that)g(they)h(are)f(all)f
Fl(pr)n(e)n(dictive,)h(lo)n(c)n(al)r(ly)262 2263 y(optimal)h(skil)r(ls)
f Ft(\(PLOS\).)h(They)g(tak)o(e)g(in)o(to)f(accoun)o(t)i(predicted)g(w)
o(orld)e(states)i(as)f(w)o(ell)f(as)262 2313 y(predicted)18
b(e\013ects)h(of)d(future)h(actions)g(in)f(order)i(to)e(determine)h
(the)h(optimal)c(primitiv)o(e)262 2363 y(action)c(from)f(a)i(lo)q(cal)f
(p)q(ersp)q(ectiv)o(e,)j(b)q(oth)e(in)f(time)g(and)h(in)f(space.)i(Ev)o
(en)f(though)g(the)g(skills)262 2412 y(are)g(predictiv)o(e,)g(the)g
(agen)o(t)g Fl(c)n(ommits)g Ft(to)g(only)f(one)h(action)f(during)h(eac)
o(h)h(cycle.)f(When)g(the)262 2462 y(time)h(comes)h(to)h(act)g(again,)f
(the)h(situation)f(is)h(completely)f(reev)n(aluated.)g(If)h(the)g(w)o
(orld)g(is)p eop
%%Page: 3 3
3 2 bop 262 224 a Ft(close)10 b(to)g(the)h(an)o(ticipated)f
(con\014guration,)g(then)h(the)f(agen)o(t)h(will)d(act)j(similarly)c
(to)j(the)h(w)o(a)o(y)262 274 y(it)k(predicted)j(on)e(previous)h
(cycles.)g(Ho)o(w)o(ev)o(er,)f(if)g(the)h(w)o(orld)e(is)i(signi\014can)
o(tly)e(di\013eren)o(t,)262 324 y(the)f(agen)o(t)g(will)f(arriv)o(e)h
(at)g(a)g(new)h(sequence)h(of)d(actions)i(rather)g(than)f(b)q(eing)g
(committed)262 374 y(to)e(a)f(previous)i(plan.)e(Again,)g(it)h(will)e
(only)i(execute)i(the)f(\014rst)f(step)i(in)d(the)i(new)g(sequence.)262
504 y Fm(2.3)47 b(F)l(ormations)262 594 y Ft(Giv)o(en)14
b(all)g(of)h(the)g(individual)f(skills)g(a)o(v)n(ailable)f(to)i(the)h
(CMUnited)f(clien)o(ts,)g(it)g(b)q(ecomes)262 643 y(a)j(signi\014can)o
(t)g(c)o(hallenge)g(to)h(co)q(ordinate)g(the)g(team)e(so)i(that)f(the)i
(pla)o(y)o(ers)e(are)h(not)g(all)262 693 y(trying)d(to)h(do)g(the)h
(same)e(thing)h(at)g(the)h(same)e(time.)g(A)o(t)h(the)h(core)g(of)e
(the)i(CMUnited-)262 743 y(98)i(co)q(ordination)g(mec)o(hanism)f(is)i
(the)h Fl(lo)n(cker-r)n(o)n(om)e(agr)n(e)n(ement)h Ft([11].)e(Based)j
(on)f(the)262 793 y(premise)15 b(that)h(agen)o(ts)g(can)f(p)q(erio)q
(dically)g(meet)g(in)h(safe,)f(full-comm)n(uni)o(cation)e(en)o(viron-)
262 843 y(men)o(ts,)j(the)h(lo)q(c)o(k)o(er-ro)q(om)f(agreemen)o(t)h
(sp)q(eci\014es)i(ho)o(w)e(they)h(should)f(act)g(when)h(in)f(lo)o(w-)
262 892 y(comm)o(uni)o(cation,)10 b(time-critical,)i(adv)o(ersarial)h
(en)o(vironmen)o(ts.)324 943 y(A)f(go)q(o)q(d)g(example)e(of)i(the)g
(use)h(of)f(the)g(lo)q(c)o(k)o(er-ro)q(om)f(agreemen)o(t)h(is)f
(CMUnited)q('s)h(abil-)262 993 y(it)o(y)j(to)g(execute)j(pre-compiled)c
(m)o(ulti-agen)o(t)f(plans)j(after)g(dead-ball)e(situations.)h(While)
262 1043 y(it)j(is)h(often)g(di\016cult)f(to)h(clear)g(the)h(ball)e
(from)f(the)j(defensiv)o(e)f(zone)h(after)f(goal)f(kic)o(ks,)262
1093 y(CMUnited-98)h(pla)o(y)o(ers)h(mo)o(v)o(e)e(to)i(pre-sp)q
(eci\014ed)i(lo)q(cations)e(and)f