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)
Crawford B.
Monfroy E.
Paredes F.
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
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