  We consider the synthesis of control policies from temporal logic
specifications for robots that interact with multiple dynamic environment
agents. Each environment agent is modeled by a Markov chain whereas the robot
is modeled by a finite transition system (in the deterministic case) or Markov
decision process (in the stochastic case). Existing results in probabilistic
verification are adapted to solve the synthesis problem. To partially address
the state explosion issue, we propose an incremental approach where only a
small subset of environment agents is incorporated in the synthesis procedure
initially and more agents are successively added until we hit the constraints
on computational resources. Our algorithm runs in an anytime fashion where the
probability that the robot satisfies its specification increases as the
algorithm progresses.
