Shlomo Zilberstein

Shlomo Zilberstein

Auto-generated profile, based on publicly available information

Shlomo Zilberstein

Manning College of Information and Computer Sciences University of Massachusetts Amherst

Research Focus & Metrics

Academic Career Length

35Years (1992-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
1 November 2002 in Mathematics of Operations Research
Verified
Journal Article
Closed access
DBDaniel S. Bernstein
Daniel S. Bernstein
RGRobert Givan
Robert Givan
NINeil Immerman
Neil Immerman
SZShlomo Zilberstein
Shlomo Zilberstein
We consider decentralized control of Markov decision processes and give complexity bounds on the worst-case running time for algorithms that find optimal solutions. Generalizations of both the fully observable case and the partially observable case that allow for decentralized control are described. For even two agents, the finite-horizon problems corresponding to both of these models are hard for nondeterministic exponential time. These complexity results illustrate a fundamental difference between centralized and decentralized control of Markov decision processes. In contrast to the problems involving centralized control, the problems we consider provably do not admit polynomial-time algorithms. Furthermore, assuming EXP ≠ NEXP, the problems require superexponential time to solve in the worst case.

1 June 2001 in Artificial Intelligence
Verified
Journal Article
Closed access
EHEric A. Hansen
Eric A. Hansen
SZShlomo Zilberstein
Shlomo Zilberstein

1 November 2004 in Journal of Artificial Intelligence Research
Verified
Journal Article
Open access
PDF file
CGC. V. Goldman
C. V. Goldman
SZS. Zilberstein
S. Zilberstein
Decentralized control of cooperative systems captures the operation of a group of decision makers that share a single global objective. The difficulty in solving optimally such problems arises when the agents lack full observability of the global state of the system when they operate. The general problem has been shown to be NEXP-complete. In this paper, we identify classes of decentralized control problems whose complexity ranges between NEXP and P. In particular, we study problems characterized by independent transitions, independent observations, and goal-oriented objective functions. Two algorithms are shown to solve optimally useful classes of goal-oriented decentralized processes in polynomial time. This paper also studies information sharing among the decision-makers, which can improve their performance. We distinguish between three ways in which agents can exchange information: indirect communication, direct communication and sharing state features that are not controlled by the agents. Our analysis shows that for every class of problems we consider, introducing direct or indirect communication does not change the worst-case complexity. The results provide a better understanding of the complexity of decentralized control problems that arise in practice and facilitate the development of planning algorithms for these problems.

14 February 2008 in Autonomous Agents and Multi-Agent Systems
Verified
Journal Article
Closed access
PDF file
SSSven Seuken
Sven Seuken
SZShlomo Zilberstein
Shlomo Zilberstein

25 August 2009 in Autonomous Agents and Multi-Agent Systems
Verified
Journal Article
Closed access
PDF file
CAChristopher Amato
Christopher Amato
DBDaniel S. Bernstein
Daniel S. Bernstein
SZShlomo Zilberstein
Shlomo Zilberstein

1 December 2004 in Journal of Artificial Intelligence Research
Verified
Journal Article
Open access
PDF file
RBR. Becker
R. Becker
SZS. Zilberstein
S. Zilberstein
VLV. Lesser
V. Lesser
CGC. V. Goldman
C. V. Goldman
Formal treatment of collaborative multi-agent systems has been lagging behind the rapid progress in sequential decision making by individual agents. Recent work in the area of decentralized Markov Decision Processes (MDPs) has contributed to closing this gap, but the computational complexity of these models remains a serious obstacle. To overcome this complexity barrier, we identify a specific class of decentralized MDPs in which the agents' transitions are independent. The class consists of independent collaborating agents that are tied together through a structured global reward function that depends on all of their histories of states and actions. We present a novel algorithm for solving this class of problems and examine its properties, both as an optimal algorithm and as an anytime algorithm. To our best knowledge, this is the first algorithm to optimally solve a non-trivial subclass of decentralized MDPs. It lays the foundation for further work in this area on both exact and approximate algorithms.