Title
Sequentially dependent meta-constraint satisfaction problem: An application to video games
Date Issued
01 January 2014
Access level
metadata only access
Resource Type
journal article
Author(s)
Pontificia Universidad Católica de Valparaíso
Publisher(s)
Editura Academiei Romane
Abstract
A Constraint Satisfaction Problem (CSP) consists in a sequence of variables holding a domain of possible values and relations among these variables called constraints. A meta-CSP can be seen as a metaproblem whose decomposition leads to a set of CSPs. The meta-variables correspond to sub-problems of the original problem, and a meta-constraint is a relation among those meta-variables. Meta-CSPs find many applications in industry, usually in processes that involve time and actions such as the control of a robot, a manufacturing process, or the scheduling of any common activity. In this paper, we introduce the notion of Sequentially Dependent Meta-CSP (SD Meta-CSP), which extends the meta-CSP in order to support applications where a dependency between sub-problems is mandatory. In this case, the meta-CSP is decomposed into a set of sub-problems {Pi, Pi+1, . . . , Pn}, but the instance of the sub-problem Pi+1 sequentially depends on the solution of the sub-problem Pi . In this work we provide a formal definition for the SD Meta-CSPs, a framework to handle it, and we illustrate its applicability to video games. In particular, we model and implement agents as SD Meta-CSPs able to autonomously play two classic games: Ms. Pac-Man and Super Mario Bros.
Start page
204
End page
216
Volume
17
Issue
2
Language
English
OCDE Knowledge area
Ingeniería de sistemas y comunicaciones
Informática y Ciencias de la Información
Subjects
Scopus EID
2-s2.0-84923933033
Source
Romanian Journal of Information Science and Technology
ISSN of the container
14538245
Sponsor(s)
Comisión Nacional de Investigación Científica y Tecnológica 11130459, 1130455, 1140897
Fondo Nacional de Desarrollo Científico y Tecnológico
Sources of information:
Directorio de Producción Científica
Scopus