--- _id: '4557' abstract: - lang: eng text: 'Planning in adversarial and uncertain environments can be modeled as the problem of devising strategies in stochastic perfect information games. These games are generalizations of Markov decision processes (MDPs): there are two (adversarial) players, and a source of randomness. The main practical obstacle to computing winning strategies in such games is the size of the state space. In practice therefore, one typically works with abstractions of the model. The diffculty is to come up with an abstraction that is neither too coarse to remove all winning strategies (plans), nor too fine to be intractable. In verification, the paradigm of counterexample-guided abstraction refinement has been successful to construct useful but parsimonious abstractions automatically. We extend this paradigm to probabilistic models (namely, perfect information games and, as a special case, MDPs). This allows us to apply the counterexample-guided abstraction paradigm to the AI planning problem. As special cases, we get planning algorithms for MDPs and deterministic systems that automatically construct system abstractions.' author: - first_name: Krishnendu full_name: Krishnendu Chatterjee id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X - first_name: Thomas A full_name: Thomas Henzinger id: 40876CD8-F248-11E8-B48F-1D18A9856A87 last_name: Henzinger orcid: 0000−0002−2985−7724 - first_name: Ranjit full_name: Jhala, Ranjit last_name: Jhala - first_name: Ritankar full_name: Majumdar, Ritankar S last_name: Majumdar citation: ama: 'Chatterjee K, Henzinger TA, Jhala R, Majumdar R. Counterexample-guided planning. In: AUAI Press; 2005:104-111.' apa: 'Chatterjee, K., Henzinger, T. A., Jhala, R., & Majumdar, R. (2005). Counterexample-guided planning (pp. 104–111). Presented at the UAI: Uncertainty in Artificial Intelligence, AUAI Press.' chicago: Chatterjee, Krishnendu, Thomas A Henzinger, Ranjit Jhala, and Ritankar Majumdar. “Counterexample-Guided Planning,” 104–11. AUAI Press, 2005. ieee: 'K. Chatterjee, T. A. Henzinger, R. Jhala, and R. Majumdar, “Counterexample-guided planning,” presented at the UAI: Uncertainty in Artificial Intelligence, 2005, pp. 104–111.' ista: 'Chatterjee K, Henzinger TA, Jhala R, Majumdar R. 2005. Counterexample-guided planning. UAI: Uncertainty in Artificial Intelligence, 104–111.' mla: Chatterjee, Krishnendu, et al. Counterexample-Guided Planning. AUAI Press, 2005, pp. 104–11. short: K. Chatterjee, T.A. Henzinger, R. Jhala, R. Majumdar, in:, AUAI Press, 2005, pp. 104–111. conference: name: 'UAI: Uncertainty in Artificial Intelligence' date_created: 2018-12-11T12:09:28Z date_published: 2005-01-01T00:00:00Z date_updated: 2021-01-12T07:59:41Z day: '01' extern: 1 main_file_link: - open_access: '0' url: http://uai.sis.pitt.edu/papers/05/p104-chatterjee.pdf month: '01' page: 104 - 111 publication_status: published publisher: AUAI Press publist_id: '157' quality_controlled: 0 status: public title: Counterexample-guided planning type: conference year: '2005' ...