.1.2 MAXQ.3.4.5

Size: px

Start display at page:

Download ".1.2 MAXQ.3.4.5"

稳赖
5 years ago
Views:

2 .1.2 MAXQ.3.4.5

3 .1.2 MAXQ.3.4.5

4 自主智能体和多智能体系统 Figure 1 : 各种智能体系统

5 Figure 2 :

6 Figure 3 : CoBot

7 MDP POMDP

8 (Puterman, 1994; Kaelbling et al., 1998) Pr(s t+1 s 0, a 0, s 1, a 1,..., s t, a t ) = Pr(s t+1 s t, a t ) (1)

9 MDP MDP S = { s 1, s 2,, s S } A = { a 1, a 2,, a A } T(s s, a) : S A S [0, 1] R(s, a) : S A R π(s) : S A [ ] V π (s 0 ) = E t 0 γt R(s i, π(s i )) V (s) = max R(s, a) + γ T(s s, a)v (s ) a A s S (2)

10 POMDP POMDP O = { o 1, o 2,, o O } Ω(o a, s ) : S A O [0, 1] h = (a 0, o 1, a 1, o 2,... a t 1, o t ) b(s) : S [0, 1] b = ζ(b, a, o) b (s ) = ηω(o s, a) s S T(s s, a)b(s) (3) POMDP MDP

11 MAXQ MDP MAXQ-OP (Bai et al., 2012a,b,c, 2013b) (PO)MDP DNG-MCTS (Bai et al., 2013a) D 2 NG-POMCP (Bai et al., 2014b) POMDP PFS (Bai et al., 2014a)

12 .1.2 MAXQ.3.4.5

13 MAXQ MDP MDP (Dietterich, 1999) M i = S i, G i, A i, R i S i G i A i R i Figure 4 : MAXQ π i : S i A i

14 π = {π 0, π 1,..., π n } π V { R(s, i) V Mi (i, s) = max a Ai Q (i, s, a) (4) Q (i, s, a) = V (a, s) + C (i, s, a) (5) C (i, s, a) = s,n Pr(s, N s, a)v (i, s ) (6) π π i (s) = argmax a A i Q (i, s, a) (7)

15 C (i, s, a) = s,n Pr(s, N s, a)v (i, s ) (8) Pr(s, N s, a) = s,s 1,...,s N 1 Pr(s 1 s, π a(s)) Pr(s 2 s 1, π a(s 1 )) Pr(s s N 1, π a(s N 1 )) Pr(N s, a) (9) s, s 1,..., s N 1 π s s

16 Pr(s s, a) = N Pr(s, N s, a) (10) C (i, s, a) = s Pr(s s, a)v (i, s ) (11) Pr(s s, a)

17 MAXQ-OP V (i, s) max a A i { V (a, s) + s Pr(s s, a)v (i, s ) } (12) d D H(i, s) H(i, s) max a Ai {V(a, s, d)+ V(i, s, d) s Pr(s s, a) V(i, s, d[i] d[i] + 1)} d[i] D[i] (13)

18 = 400 (x, y) R Y B G In R Y B G 6 North South East West Figure 5 : Pickup Putdown

19 Table 1 : * ms Figure 6 : MAXQ-OP 3.93 ± ± 0.16 LRTDP 3.71 ± ± 3.71 AOT 3.80 ± ± 2.37 UCT ± ± 4.24 * 4.01 ± 0.15.

20 RoboCup 2D ms Figure 7 : RoboCup 2D.

21 RoboCup 2D

2D WrightEagle 2006 2009 2011 2013 2014 2005

22 2D WrightEagle MAXQ-OP 2009 Figure 8 :

23 MAXQ-OP Figure 9 : MAXQ

24 RTDP AOT UCT [s 1 s 2 s 3 s H ] g MAXQ-OP [s 1 s H1 ] [g 1 /s 1 s H 2 ] [g 2 /s 1 s H3 ] g MAXQ-OP

25 MAXQ MAXQ-OP MAXQ MAXQ-OP RoboCup 2D WrightEagle

26 .1.2 MAXQ.3.4.5

27 T(s s, a) s T(s s, a) MCTS

28 MCTS Figure 10 : (Chaslot et al., 2008).

29 MCTS MAB N CR [ T ] R T = E (X a X at ) t=1 (14) Figure 11 : MAB

30 MAB Figure 12 :

31 Thompson MAB a b Pr(a ) = 0.3 Pr(b ) = 0.7 (Thompson, 1933) [ ] Pr(a) = 1 a = argmax E [X a θ a ] Pr(θ a Z) dθ (15) a a Z θ a X a

32 Thompson θ a Pr(θ a Z) E [X a θ a ] Thompson MAB UCB

33 MDP POMDP MCTS Thompson

34 DNG-MCTS DNG-MCTS Dirichlet-NormalGamma MCTS X s,π s π X s,a,π s a π X s,a,π = R(s, a) + γx s,π (16) s T(s s, a)

35 DNG-MCTS X s,π X s,a,π X s,π N(µ s, 1/τ s ); (µ s, τ s ) NormalGamma(µ s,0, λ s, α s, β s ) T( s, a) Dirichlet(ρ s,a ) Thompson 1

36 D 2 NG-POMCP D 2 NG-POMCP Dirichlet-Dirichlet-NormalGamma partially observable Monte-Carlo planning X b,a b a X s,b,π s, b π X b,π b π Pr(X b,a = r) = 1[R(s, a) = r]b(s) (17) s S f Xb,π (x) = s S b(s)f Xs,b,π (x) (18)

37 D 2 NG-POMCP X b,a X s,b,π X b,π X b,a Multinomial(p b,a ); p b,a Dirichlet(ψ b,a ) X s,b,π N(µ s,b, 1/τ s,b ); (µ s,b, τ s,b ) NormalGamma(µ s,b,0, λ s,b, α s,b, β s,b ) Ω( b, a) Dirichlet(ρ b,a ) Thompson 1

38 DNG-MCTS MDP CTP Racetrack UCB UCT

39 MDP n 3 m Figure 13 : CTP

40 Table 2 : 20 CTP UCT DNG UCT DNG ± ± ± ± ± ± ± ± ± ± ± ± ± ± ± ± ± ± ± ± ± ± ± ± ± ± ± ± ± ± ± ± ± ± ± ± ± ± ± ±3 total

41 ,534 Figure 14 :

42 Avg. Accumulated Cost UCT DNG-MCTS Number of Iterations Figure 15 :

43 D 2 NG-POMCP POMDP RockSample PocMan UCB POMCP

44 RockSample RockSample[7,8] 12, Figure 16 : RockSample[7,8].

45 Table 3 : RockSample 1 RockSample [7, 8] [11,11] [15,15] States s 12, ,808 7,372,800 AEMS ± 0.22 N/A N/A HSVI-BFS ± 0.22 N/A N/A SARSOP ± ± 0.11 N/A POMCP ± ± ± 0.28 D 2 NG-POMCP ± ± ± 0.24

46 Ghost ,024 Figure 17 :

47 Avg. Discounted Return POMCP D 2 NG-POMCP Number of Iterations (a) - Avg. Discounted Return POMCP D 2 NG-POMCP 1e Avg. Time Per Action (Seconds) (b) - Figure 18 :

48 MDP POMDP DNG-MCTS D 2 NG-POMCP MCTS Thompson 1

49 .1.2 MAXQ.3.4.5

50 Tracking-by-detection

51 ID Figure 19 :

52 CoBot Figure 20 :

54 HMM S = {s 0, s 1,..., s n } O = {o 1, o 2,..., o m } Pr(S S) Pr(O S) Pr(S t O 0, O 1,..., O t )

55 S = {s 0, s 1,..., s n } s = (x, y, ẋ, ẏ) Figure 21 :

56 S = {s 0, s 1,..., s n } O = {o 0, o 1,..., o m } F O M S O F = S M F-M O S = { F 0, M 0,..., F z, M z } Poisson ν S ξ Pr(O S) = F,M O S (ντ) F e ντ o F Pr(O F S M) Pr(o ) ( S ξτ) M e S ξτ M! 1 ( S ) (19) M

57 0 i min{ O, S } ( O i )( S i ) i! = Ω(( max{ O, S } e ) min{ O, S } ) F-M

58 Figure 22 : X = {s 0, s 1,..., s n } N Pr(S t O t ) P t = { X (0) t N i=1 w = 1, w(0) t, X(1) t, w(1) t,..., X(N), w (N) t } (20) t

59 PFS PETS2009 (Ferryman & Shahrokni, 2009) fps (x, y, h, w) c

60 PETS2009 数据集定性实验结果 Figure 23 : PETS2009 数据集定性实验结果

61 PETS2009 Table 4 : PETS2009 Algorithm MOTA MOTP IDS MT FM PFS 1 (proposed) 93.1% 76.1% PFS 12 (proposed) 90.6% 74.5% Milan (2014) 90.6% 80.2% Milan et al. (2013) 90.3% 74.3% Segal & Reid (2013) 92% 75% Segal & Reid (2013) 2 90% 75% Zamir et al. (2012) % 69.0% Andriyenko & Schindler (2011) 81.4% 76.1% Breitenstein et al. (2011) % 79.7%

62 Figure 24 : CoBot

63 PETS2009 CoBot

64 .1.2 MAXQ.3.4.5

65 MAXQ-OP MAXQ MAXQ DNG-MCTS D 2 NG-POMCP Thompson PFS

66 MAXQ-OP DNG-MCTS D 2 NG-POMCP PFS

67 Bai, A., Simmons, R., Veloso, M., & Chen, X. (2014a), Intention-aware multi-human tracking for human-robot interaction via particle filtering over sets, In AAAI 2014 Fall Symposium: AI for Human-Robot Interaction (AI-HRI 2014), Arlington, United States Bai, A., Wu, F., Zhang, Z., & Chen, X. (2014b), Thompson sampling based Monte-Carlo planning in POMDPs, (In Proceedings of the 24th International Conference on Automated Planning and Scheduling (ICAPS 2014)pp.29 37), Portsmouth, United States Bai, A., Wu, F., & Chen, X. (2013a), Bayesian mixture modelling and inference based Thompson sampling in Monte-Carlo tree search, (In Advances in Neural Information Processing Systemspp ) Bai, A., Wu, F., & Chen, X. (2013b), Towards a principled solution to simulated robot soccer, (In RoboCup 2012: Robot Soccer World Cup XVIvol.7500pp ), Springer Bai, A., Wu, F., & Chen, X. (2012b), Online planning for large mdps with maxq decomposition, (In Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems-Volume 3pp ), International Foundation for Autonomous Agents and Multiagent Systems Bai, A., Wu, F., & Chen, X. (2012c), Online planning for large MDPs with MAXQ decomposition, In Proc. of the Autonomous Robots and Multirobot Systems workshop (at AAMAS 2012) Bai, A., Chen, X., MacAlpine, P., Urieli, D., Barrett, S., & Stone, P. (2012a), WrightEagle and UT Austin Villa: RoboCup 2011 simulation league champions, (In RoboCup 2011: Robot Soccer World Cup XVvol.7416pp.1 12), Springer

69 I Andriyenko, A., & Schindler, K. (2011), Multi-target tracking by continuous energy minimization, (In Computer Vision and Pattern Recognition (CVPR), 2011 IEEE Conference onpp ), IEEE. Bai, A., Chen, X., MacAlpine, P., Urieli, D., Barrett, S., & Stone, P. (2012a), WrightEagle and UT Austin Villa: RoboCup 2011 simulation league champions, (In RoboCup 2011: Robot Soccer World Cup XVvol.7416pp.1 12), Springer. Bai, A., Simmons, R., Veloso, M., & Chen, X. (2014a), Intention-aware multi-human tracking for human-robot interaction via particle filtering over sets, In AAAI 2014 Fall Symposium: AI for Human-Robot Interaction (AI-HRI 2014), Arlington, United States. Bai, A., Wu, F., & Chen, X. (2012b), Online planning for large mdps with maxq decomposition, (In Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems-Volume 3pp ), International Foundation for Autonomous Agents and Multiagent Systems. Bai, A., Wu, F., & Chen, X. (2012c), Online planning for large MDPs with MAXQ decomposition, In Proc. of the Autonomous Robots and Multirobot Systems workshop (at AAMAS 2012). Bai, A., Wu, F., & Chen, X. (2013a), Bayesian mixture modelling and inference based Thompson sampling in Monte-Carlo tree search, (In Advances in Neural Information Processing Systemspp ). Bai, A., Wu, F., & Chen, X. (2013b), Towards a principled solution to simulated robot soccer, (In RoboCup 2012: Robot Soccer World Cup XVIvol.7500pp ), Springer. Bai, A., Wu, F., Zhang, Z., & Chen, X. (2014b), Thompson sampling based Monte-Carlo planning in POMDPs, (In Proceedings of the 24th International Conference on Automated Planning and Scheduling (ICAPS 2014)pp.29 37), Portsmouth, United States.

70 II Breitenstein, M. D., Reichlin, F., Leibe, B., Koller-Meier, E., & Van Gool, L. (2011), Online multiperson tracking-by-detection from a single, uncalibrated camera, IEEE Transactions on Pattern Analysis and Machine Intelligence, 33(9), Chaslot, G., Bakkes, S., Szita, I., & Spronck, P. (2008), Monte-carlo tree search: A new framework for game AI, In C. Darken, & M. Mateas (Eds.) Proceedings of the Fourth Artificial Intelligence and Interactive Digital Entertainment Conference, October 22-24, 2008, Stanford, California, USA, The AAAI Press. URL Dietterich, T. G. (1999), Hierarchical reinforcement learning with the maxq value function decomposition, Journal of Machine Learning Research, 13(1), 63. Ferryman, J., & Shahrokni, A. (2009), PETS2009: Dataset and challenge, (In 2009 Twelfth IEEE International Workshop on Performance Evaluation of Tracking and Surveillance (PETS-Winter)pp.1 6), IEEE. Kaelbling, L. P., Littman, M. L., & Cassandra, A. R. (1998), Planning and acting in partially observable stochastic domains, Artificial Intelligence, 101(1-2), Kocsis, L., & Szepesvári, C. (2006), Bandit based Monte-Carlo planning, (In European Conference on Machine Learningpp ). Milan, A. (2014), Energy Minimization for Multiple Object Tracking, PhD, TU Darmstadt, Darmstadt. Milan, A., Schindler, K., & Roth, S. (2013), Detection-and trajectory-level exclusion in multiple object tracking, (In Computer Vision and Pattern Recognition (CVPR), 2013 IEEE Conference onpp ), IEEE. Puterman, M. L. (1994), Markov Decision Processes: Discrete Stochastic Dynamic Programming, John Wiley & Sons, Inc.

71 III Segal, A. V., & Reid, I. (2013), Latent data association: Bayesian model selection for multi-target tracking, (In Computer Vision (ICCV), 2013 IEEE International Conference onpp ), IEEE. Silver, D., & Veness, J. (2010), Monte-Carlo planning in large POMDPs, (In Advances in Neural Information Processing Systemspp ). Thompson, W. R. (1933), On the likelihood that one unknown probability exceeds another in view of the evidence of two samples, Biometrika, 25, Zamir, A. R., Dehghan, A., & Shah, M. (2012), Gmcp-tracker: Global multi-object tracking using generalized minimum clique graphs, (In Computer Vision ECCV 2012pp ), Springer.

72 MDP π(s) : S A [ ] V π (s 0 ) = E t 0 γt R(s i, π(s i )) { V (s) = max a A R(s, a) + γ s S T(s s, a)v (s ) } (21) π (s) = argmax V (s) (22) a A

73 POMDP π(b) : B A B = {b} { V (b) = max a A r(b, a) + γ o O Ω(o b, a)v (ζ(b, a, o)) } (23) r(b, a) = s S b(s)r(s, a) π (b) = argmax V (b) (24) a A

74 RoboCup 2D MDP 23

75 Full MAXQ-OP Random Pass Dribble Hand-coded Pass Dribble 3 Dribble 3 Pass

76 Success WrightEagle Failure x < 10 Timeout > Figure 25 :

77 Table 5 : WrightEagle Success Failure Timeout Full Random Hand-coded MAXQ-OP MAXQ-OP

78 Full BrainsStomers08 RoboCup 2008 Helios10 RoboCup 2010 Helios11 RoboCup 2011 Oxsy11 100

79 Table 6 : WrightEagle BrainsStomers : : ± 7.5% Helios : : ± 5.0% Helios : : ± 8.8% Oxsy : : ± 5.6%

80 UCB log T UCB(a) = R(a) + c N(a) (25) R(a) a T N(a) a c MAB a = argmax UCB(a) (26) a A

81 UCT UCT (Kocsis & Szepesvári, 2006): log N(s) UCB(s, a) = Q(s, a) + c (27) N(s, a) 1 c c

82 UCT POMDP POMCP (Silver & Veness, 2010) UCB(h, a) = Q(h, a) + c log N(h) N(h, a) (28) 1 c c

83 ˆX t π( X t 1, O t ) w t w t 1 m t o t p t m t = Pr( ˆX t X t 1 ) o t = Pr(O t ˆX t ) p t = π( ˆX t X t 1, O t )

84 Figure 26 :

85 P = {X X Pr( X), X P} P = {X X π r ( X ), X P } Pr(X X) Pr(X P ) π r (X X) Pr(X P ) Figure 27 :

86 PETS2009 λ (1/s) 0.0 µ (1/s) 0.02 σ p (m 2 /s) 1.0 ν (1/s) 6.0 ξ (1/s) 2.0 τ (s) 0.14 T 0.1 T Σ 0.5I R 0.4 N 128 H EM 10 Table 7 : PETS2009 PFS

87 CLEAR MOT MOTA ( t MOTA = 1 (g ) t + a t 2n t + m t ) t g 100% (29) t g t a t n t m t ID

88 CLEAR MOT MOTP ( MOTP = 1 t 1 i n t d (i) t t n t n t d (i) t ) 100% (30)

89 {X 0,..., X N } {h 0,..., h z } H(h) H(P t ) s = 1 H(h) c = H(h) N s H(h) s [0, 1] Figure 28 :

90 t C t s X X P t l(s) C t f h P = {f h h C t } P = argmax P EM max Pr(P t, l P) (31) l E- P l N M- l P MLE l P l P l P

91 E- l (k) = argmax l Pr(P t, l P (k 1) ) s X f l(s)(s) N M- P (k) = argmax P Pr(P t, l (k 1) P) MLE O t l P l P l P

MAXQ BA ( ) / 20

MAXQ BA ( ) / 20 MAXQ BA11011028 2016 6 7 () 2016 6 7 1 / 20 1 2 3 4 () 2016 6 7 2 / 20 RoboCup 2D 11 11 100ms/ 1: RoboCup 2D () 2016 6 7 3 / 20 2: () 2016 6 7 4 / 20 () 2016 6 7 5 / 20 Markov Decision Theory [Puterman,