TY - JOUR
T1 - Sequentially dependent meta-constraint satisfaction problem
T2 - An application to video games
AU - Soto, Ricardo
AU - Crawford, Broderick
AU - Monfroy, Eric
AU - Paredes, Fernando
PY - 2014
Y1 - 2014
N2 - 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.
AB - 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.
KW - Artificial intelligence
KW - Constraint satisfaction problem
KW - Video-games
UR - http://www.scopus.com/inward/record.url?scp=84923933033&partnerID=8YFLogxK
M3 - Article
AN - SCOPUS:84923933033
SN - 1453-8245
VL - 17
SP - 204
EP - 216
JO - Romanian Journal of Information Science and Technology
JF - Romanian Journal of Information Science and Technology
IS - 2
ER -