Distributed Problem Solving and Planning

Presentation on theme: "Distributed Problem Solving and Planning"— Presentation transcript:

1 Distributed Problem Solving and Planning
안재현

2 개요 Introduction Task-Sharing Result-Sharing/Communication
Planning : Conflict의 제거 Conclusion

3 Introduction : Tower of Hanoi
Let f(n) = n개의 접시를 옮기는 시간 f(n) = f(n-1) f(n-1) 2n - 1 another agent another agent f(n) = 2 allocation time+ f(n-1)+ 1 work time = about k * n ( k = const) O(2n) becomes O(n) !

4 Really? Of course not! Tower of Hanoi 문제에서 n = 30일 때
single agent : time of about 1,000,000,000 multi-agent : time of about 30 * k , but about 2,000,000,000 agents and about 1,000,000,000 communications is needed!

5 How can we control the problems?
task-sharing result-sharing/communication f(n) f(n-1) f(n-1) more problems planning : conflict를 어떻게 해결할 것인 가?

6 Task Sharing Task Sharing Finding Agents Introduction
Result Sharing / Communication Planning : Conflict의 제거 Conclusion

7 Finding Agents Task Sharing in Heterogeneous Systems
assignment of subproblems is very complex agents can have a table of agents When all agents of the table are not available? Broadcasting Contracting Retry Announcement Revision Alternation Decomposition

8 Result Sharing / Communication
Introduction Task Sharing Result Sharing / Communication Why Communication is restricted? Planning : Conflict의 제거 Conclusion

9 Why Communications should be Restricted?
K? J? S? A! A! A! A! A! Distraction: 모든 agent가 search space 상에서 동일한 경로로 이동함.

10 Planning : Conflict 의 제거1/2
Introduction Task Sharing Result Sharing / Communication Planning : Conflict의 제거 Distributed Planning and Distributed Plans Distributed Planning and Execution Conclusion

11 Distributed Planning and Distributed Plans
Plan Merging Iterative Plan Formation Negotiation in Distributed Planning

12 Plan Merging 여러 plan이 세워진 경우, 이들을 함께 실행할 경우 conflict가 발생하는지 찾는다.
각 plan 에서 다른 agent와 상호작용 (일반적으로 communication)하는 경우만을 골라낸다. 한 가지씩 match시키며 문제가 발생하는지 check한다.

13 Iterative Plan Formation
Local planning 을 global plan set의 behavior-space에서의 search로 간주하여Conflict를 최소화하는 방향으로 이동함으로써 수행한다. plan combination search : A* heuristic 이용 distributed hierarchical planning hierarchical behavior-space search using multiple levels of abstraction f(n) f(n-1) 1 f(n-1)

14 Abstraction level에서의 decision
Communicate more details

15 Negotiation in Distributed Planning
Conflict 가 detect된 경우 해당 agent 사이에 negotiation을 수행함 agent들 중 형편이 나은 쪽이 양보함 ex) 시간여유가 더 많은 것 가능한 대안의 수가 많은 것 등. 일종의 cooperation으로 볼 수 있음 각 agent는 honest한 것으로 가정함.

16 Planning : Conflict 의 제거2/2
Introduction Task Sharing Result Sharing / Communication Planning : Conflict의 제거 Distributed Planning and Distributed Plans Distributed Planning and Execution Conclusion

17 Distributed Planning and Execution
Coordination, Planning, Execution의 관계 Post-Planning Coordination Pre-Planning Coordination Interleaved Planning, Coordination, and Execution Runtime Plan Coordination Without Communication

18 Post-Planning Coordination 1/2
Planning → Coordination → Execution 모든 agent가 각각 planning을 수행한다. Plan을 종합하여 coordinate한다. Most classical strategy 문제점: Execution 과정에서 예상치 못한 failure가 발생한 경우, coordinated plan set 전체가 failing할 위험이 있다.

19 Post-Planning Coordination 2/2
해결책 1: contingency planning 각 agent는 expected plan 뿐 아니라, 가능한 모든 alternative case 를 준비한다. 해결책 2: monitoring and replanning execution 과정을 monitoring하여, 문제가 detect되면 replanning을 수행한다. Replanning with Coordination ⇒ overhead Planning only abstraction level execution time에 세부사항을 replanning coordination 과정이 필요하지 않음.

20 Pre-Planning Coordination
Coordination → Planning → Execution 가능한 Coordination restrictions 에 따라 Coordination을 수행함 ex) Social Law 자동차를 운전할 경우, 다른 agent(운전수)의 planning에 대해 알지 못하는 상태에서 교통법규에 따라 수행(즉 운전) 을 coordination 하는 것이 가능하다.

21 Interleaved Planning, Coordination, and Execution
Execution time에 planning과 coordination이 수행되는 strategy more flexible than Pre- or Post- planning of coordination

22 Runtime Plan Coordination Without Communication
In some applications, runtime recoordination is needed when agents cannot or should not communicate. Observation-based plan coordination Interference

23 Conclusion Task-Sharing Result-Sharing/Communication Planning