The problem of decentralized decision making under uncertainty has received significant attention over the past few years. It has applications in diverse fields that include robotics, networking.
In this work, we look at decentralized decision making in environment where the actions have probabilistic outcomes and communication is limited and in which the system state is only partially observable.
We focus on using a model called a decentralized partially observable Markov decision processes. This framework is very general, incorporating stochastic action effects, uncertainty about the system state, and limited communication. Decentralized control of multiple agents is NEXP-hard.
We propose a sample-based approximate algorithm. Point-based BPI first select a set of belief points, and monotonically increase the value for all belief points. This approach allows to restrict belief points to reachable regions of the belief.
불확실성이 있는 환경에서 분산되어 있는 에이전트의 행동을 결정하는 것은 중요하면서도 어려운 문제이다. 이것은 로보틱스, 네트워킹 등 여러 분야에서 볼 수 있다. 예를 들어 공동의 임무를 수행하는 다수의 화성 탐사 로봇은 매우 불확실한 환경에 놓여있으므로, 센서를 통해 얻은 정보를 이용하여 외부 환경에 대해 추정하고 이를 바탕으로 결정을 내려야 한다. 또한 로봇 서로간의 통신이 매우 제한적이므로 다른 로봇들의 행동까지도 추정하면서 공동의 임무를 수행할 수 있어야 한다. 본 논문에서는 특히 에이전트들의 목표가 모두 동일하고, 정보 교환에 제약이 있으며, 환경 상태를 직접 알지 못하는 문제를 다룬다. 우리는 multi-agent planning 문제를 위한 형식적 프레임워크인 decentralized POMDP에 초점을 맞출 것이다. Decentralized POMDP의 최적 정책을 구하는 것은 계산적으로 매우 어렵다는 것이 알려져 있다. 그러므로 우리는 근사 알고리즘을 제안하고자 한다. 본 논문에서 제안하는 point-based BPI는 수집(sample)된 belief에 집중하는 알고리즘이다. 이 방법은 기존 알고리즘에 비해 계산 시간을 적게 소모면서도 더 나은 정책을 구하도록 한다.
