JAIST Reposi https://dspace.j Title 動的な環境に対応するプラン再生成システム Author(s)Chen, Lifeng Citation Issue Date 2014-03 Type Thesis or Dissertation Text version author URL http://hdl.handle.net/10119/12008 Rights Description Supervisor: 東条敏, 情報科学研究科, 修士 Japan Advanced Institute of Science and
2014 3
Nguyen Minh Le 1210032 : 2014 2 Copyright cfl 2014 by Chen Lifeng 2
1 1 2 3 2.1 STRIPS : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 3 2.2 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 7 2.2.1 : : : : : : : : : : : : : : : : : : : : : : : : 7 2.3 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 8 2.3.1 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 8 2.3.2 : : : : : : : : : : : : : 10 3 3-BLOCKS 18 3.1 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 18 3.2 3 BLOCKS : : : : : : : : : : : : : : : : : : : : : : : : : : : : 20 3.2.1 : : : : : : : : : : : : : : : : : : : : : : : : : : : : 20 3.2.2 3-BLOCKS : : : : : : : : : : : : : : : : : : : : : : : : : : : 20 3.2.3 3-BLOCKS : : : : : : : : : : : : : : : : : : : : : : : : 22 3.2.4 : : : : : : : : : : : : : : : : : : : : : : : : 23 3.3 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 26 3.4 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 28 4 30 4.1 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 30 4.2 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 30 4.2.1 : : : : : : : : : : : : : : : : : : : : 31 4.2.2 : : : : : : : : : : : : : : : : : : : : : : : : : : 31 4.3 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 33 4.3.1 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 33 4.3.2 : : : : : : : : : : : : : : : : : : : : : : : : : : : : 33 4.3.3 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 38 4.4 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 39 i
5 41 5.1 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 41 5.2 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 41 ii
1 7 1970 STRIPS [1] SHRDLU SHRDLU Helmet[2] GRAPHPLAN[3] SATPLAN[4] HTN 2006 [4] 1
2
2 2.1 STRIPS STRIPS STRIPS pickup(a) pickup(a) clear(a), ontable(a), handempty ontable(a), handempty holdng(a) A A A A STRIPS 2.1 2.2 3
2.1: 4
2.2: 5
2.3: 6
2.3 2.2 backtraking 2.2.1 8 8 8 8 8 ( 2.4) 2.5 2.4: 2.5: 7
2.3 2.3.1 10 10 100 1000 10 2.6 2.6: [1] Winograd SHRDLU Winograd 8
1970 4 1. 2. 3 3. 4. 2 2.7 C B C B C A B 3.2 C B C A B A B C B C 9
C B C B A A B 2.7: 2.3.2 STRIPS STRIPS 1971 Fikes STRIPS STRIPS 3.3 10
1. 2 3 2. 3. stack(x,y) clear(y) and holding(x) clear(y) and holding(x) armempty andon(x,y unstack(x,y) on(x,y) and clear(y) and armempty on(x,y) and armempty holding(x) and clear(y) pickup(x) clear(x) and ontable(x) and armempty ontable(x) and armempty holding(x) putdown(x) holding(x) holding(x) ontable(x) and armempty stack(x,y) Y X unstack(x,y) Y X pickup(x) X putdown(x): X clear(x) X holding(x) X on(x,y) Y X ontable(x) X armempty 11
2.8 unstack(b,a) stack(b,d) pickup(c) stack(c,a) on(b,a) ontable(a) ontable(c) ontable(d) clear(b) clear(c) clear(d) armempty on(c,a) on(b,d) ontable(a) ontable(d) 2.8: on(c,a) and on(b,d) and ontable(a) and ontable(d) 12
a b d a d on(b,a) and ontable(a) and ontable(c) and ontable(d) and clear(b) and clear(c) and clear(d) and armempty 4 and and ontable(a) ontable(b) 2 on(c,a) on(b,d) on(c,a) and on(b,d) and ontable(a) and ontable(d) and on(c,a) on(b,d) on(c,a) and c a = on(c,a) c a stack(c,a) stack(c,a) clear(a) and holding(c) 13
on(c,a) clear(a) and holding(c) stack(c,a) on(b,d) on(c,a) and on(b,d) and ontable(a) and ontable(d) clear(a) holding(c) clear(a) and holding(c) stack(c,a) on(b,c) on(c,a) and on(b,d) and ontable(a) and ontable(d) clear(a) clear(a) unstack(b,a) on(b,a) clear(b) armempty on(b,a) and clear(b) and armempty unstack(b,a) holding(c) clear(a) and holding(c) stack(c,a) on(b,d) on(c,a) and on(b,d) and ontable(a) and ontable(d) 3 4 and unstack(b,a) unstack(b,a) unstack(b,a) 2.9 14
ontable(a) holding(b) ontable(c) ontable(d) clear(b) clear(c) clear(d) armempty on(c,a) on(b,d) ontable(a) ontable(d) 2.9: unstack(b,a) holding(c) clear(a) and holding(c) stack(c,a) on(b,d) on(c,a) and on(b,d) and ontable(a) and ontable(d) holding(c) holding(c) holding(c) pickup(c) unstack(c,x) 2 2 15
pickup(c) unstack(c,x) c pickup(c) c X unstack(c,x) c pickup(c) ontable(c) clear(c) armempty ontable(c) and clear(c) and armempty pickup(c) clear(a) and holding(c) stack(c,a) on(b,d) on(c,a) and on(b,d) and ontable(a) and ontable(d) 2 armempty armempty stack(b,x) putdown(b) 2 stack(b,x) putdown(b) on(b,x) stack(b,x) putdown(b) on(b,d) X d stack(b,d) clear(d) holding(b) clear(d) and holding(b) stack(b,d) ontable(c) and clear(c) and armempty pickup(c) clear(a) and holding(c) stack(c,a) on(b,d) on(c,a) and on(b,d) and ontable(a) and ontable(d) on(b,d) on(c,a) and on(b,d) and ontable(a) and ontable(d) stack(b,d) pickup(c) stack(c,a) on(b,d) armempty stack(b,d) on(b,d) 16
on(c,a) and on(b,d) and ontable(a) and ontable(d) unstack(b,a) stack(b,d) pickup(c) stack(c,a) 17
3 3-BLOCKS 3-BLOCKS 3 BLOCKS 3.1 3.1 3 BLOCKS 18
3.1: 19
3.2 3 BLOCKS 3.2.1 3.2: 3.2 B E B E 2 3.2.2 3-BLOCKS 1 2 3 3.3 3.3: 1 20
3.4 3.4: 3 3.5 3.5: 1 3.6 1 B, K, x B, K, x 21
3.6: 144 3.7 3.7: 4 3 3-BLOCKS 3-BLOCKS 3.2.3 3-BLOCKS 3-BLOCK clear(x) and clear(y) and clear(z) clear(x) and clear(y) and on(z,x) clear(x) and on(x,y) and on(y,z) 22
ontable(x) and ontable(y) and ontable(z) ontable(x) and ontable(y) and on(z,x) ontable(x) and on(x,y) and on(y,z) 3.11 3.8: 3 3.2.4 10 2 3-BLOCKS 10 2 3 100 3-BLOCKS 23
8X8 3.9 3.9 3-BLOCKS 3-BLOCKS 1 A 4 5 4 5 2 6 2 6 2 1 2 1 2 1 24
1 1 3 3.9: 25
3.3 3-BLOCKS 3-BLOCKS 3.11 3.10: 3.11 3.11: 3.11 3.12 26
3.12: 27
3.4 STRIPS STRIPS STRIPS 3.13 ontable(e) clear(e) on(b,h) clear(b) on(k,i) clear(k) ontable(e) ontable(k) ontable(b) 3.13: 3.13 E, B, K B, K, E STRIPS STRIPS B, K,E B, K,E STRIPS 28
3-BLOCKS 3.13 STRIPS : unstack(b,h) putdown(b) unstack(k,i) putdown(k) 29
4 4.1 3-BLOCKS 3-BLOCKS 4.2 3-BLOCKS C ASCII WINDOWS 80 80 STRIPS PROLOG PROLOG stack(x,y) clear(y) and holding(x) clear(y) and holding(x) armempty and on(x,y unstack(x,y) on(x,y) and clear(y) and armempty on(x,y) and armempty holding(x) and clear(y) pickup(x) 30
clear(x) and ontable(x) and armempty ontable(x) and armempty holding(x) putdown(x) holding(x) holding(x) ontable(x) and armempty 3-BLOCKS PROLOG C 3-BLOCKS PROLOG 4.2.1 4.1: 4.2: 3-BLOCKS 5 80 N B I B N B = I B (0:2»» 0:8) 10 80 5 10 40 4.2.2 31
32 4.3:
4.3 4.3.1 3 BLOCKS R B 4.3 10 80 f f = R B I B 100% 1 2 3 4 5 10BLOCKS 30.0% 30.0% 90.0% 90.0% 0.0% 20BLOKKS 90.0% 90.0% 90.0% 90.0% 30.0% 30BLOCKS 20.0% 70.0% 40.0% 100.0% 20.0% 40BLOCKS 97.5% 7.5% 97.5% 60.0% 97.5% 50BLOCKS 100.0% 96.0% 12.0% 42.0% 90.0% 60BLOCKS 100.0% 25.0% 100.0% 20.0% 100.0% 70BLOCKS 34.3% 98.6% 94.3% 60.0% 12.8% 80BLOCKS 97.5% 97.5% 97.5% 41.3% 97.5% 4.1: 10 80 3-BLOCKS 4.3.2 4.4 4.11 10 80 5 3-BLOCKS 3-BLOCKS 33
10 3-BLOCKS 4.4: 10 20 20% 80% 4.5: 20 34
30 20 20 4.6: 30 40 30 40 4.7: 40 35
50 40 40 4.8: 50 50 50 4.9: 60 36
60 4.10: 70 80 20 4.11: 80 37
4.3.3 4.3 3-BLOCKS t B = O t N t O t 100% 1 2 3 4 5 10BLOCKS 12.4% 6.0% 44.9% 6.6% -3.9% 20BLOKKS 69.1% 54.8% 53.1% 63.4% 24.8% 30BLOCKS 30.3% 62.9% 37.9% 67.5% 36.5% 40BLOCKS 72.7% 8.0% 76.5% 57.8% 75.5% 50BLOCKS 74.7% 47.0% 21.8% 56.2% 79.5% 60BLOCKS 77.3% 37.6% 30.6% 21.0% 73.4% 70BLOCKS 44.1% 62.5% 84.1% 69.5% 34.4% 80BLOCKS 66.1% -5.3% 57.3% 52.9% 66.4% 4.2: 10 80 3-BLOCKS 4.12: 38
4.4 10 4.4 5 4.13 4.14 3-BLOCKS 0 10 1 3 3-BLOCKS 4.13: 10BLOCKS 5 4.14: 10BLOCKS 5 10BLOCKS 20BLOCKS 30BLOCKS 40BLOCKS 13.2% 53.0% 47.0% 58.2% 50BLOCKS 60BLOCKS 70BLOCKS 80BLOCKS 55.8% 40.0% 58.9% 47.5% 4.3: 10 80 3-BLOCKS 10BLOCKS 20BLOCKS 30BLOCKS 40BLOCKS 48.0% 78.0% 50.0% 72.0% 50BLOCKS 60BLOCKS 70BLOCKS 80BLOCKS 68.0% 69.0% 57.7% 86.3% 4.4: 10 80 3-BLOCKS 4.12 60% 50% 90% 4.3 20 50% 70 39
5 4.10 4.15 4.16 4.15: 70BLOCKS 5 4.16: 70BLOCKS 5 4.15 Z b e T J R A i o 3 9 70 12 8% 34.4% 40
5 5.1 3 BLOCKS 3-BLOCKS 100% 10% 20% 5.2 3-BLOCKS 3-BLOCKS 41
3-BLOCKS 3-BLOCKS 3-BLOCKS 42
43
[1] R. Fikes and N. Nilsson STRIPS: a new approach to the application of theorem proving to problemsolving Artificial Intelligence 2:189-208. [2] Helmert, M., On the complexity of planning in transportation domains In Cesta, A. Barrajo, D. (Eds.) Sixth European Conference on Planning (ECP-01) Toledo, Spain. Springer-Verlag, 2001 [3] Kautz, H., Unifying SAT-based and Graph-based Planning, Proceedings of IJCAI-99, pp.318-325, 1999 [4], SAT SAT. AI, 106(38), pp.19-24, 2006 [5],,, 1964. [6] Hayashi, H., Tokura, S., Hasegawa, T., and Ozaki, F., An Incremental Forward-Chaining HTN, Planning Agent in Dynamic Domains, Springer, 2006, pp.171-187 [7],,. NC, 107(542), pp.295-300, 2008 [8] Richard E.Fikes, Peter E. Hart and Nils J.Nilsson Learning and Executing Generalized Robot Plans I, Stanford Research Institute. NC, Menlo Park, California 94025, Artificial Intelligence 3 (1972), 251-288 [9], D-I Vol. J87-D-I No.6 2004 6 [10], Vol.12No.11995 44
[11] D. Shapiro and P. Langley Separating skills frompreference: Using learning to programby reward, Proc. Nineteenth International Conference on Machine Learning, Sydney, 2002 [12], 16 5 2001 9 45