Classical planning algorithms on the atari video games

Nir Lipovetzky, Miquel Ramirez, Hector Geffner

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    Abstract

    The Atari 2600 games supported in the Arcade Learning Environment (Bellemare et al. 2013) all feature a known initial (RAM) state and actions that have deterministic effects. Classical planners, however, cannot be used for selecting actions for two reasons: first, no compact PDDL-model of the games is given, and more importantly, the action effects and goals are not known a priori. Moreover, in these games there is usually no set of goals to be achieved but rewards to be collected. These features do not preclude the use of classical algorithms like breadth-first search or Dijkstra's algorithm, but these methods are not effective over large state spaces. We thus turn to a different class of classical planning algorithms introduced recently that perform a structured exploration of the state space; namely, like breadth-first search and Dijkstra's algorithm they are "blind" and hence do not require prior knowledge of state transitions, costs (rewards) or goals, and yet, like heuristic search algorithms, they have been shown to be effective for solving problems over huge state spaces. The simplest such algorithm, called Iterated Width or IW, consists of a sequence of calls IW(1), IW(2),..., IW(fc) where IW(i) is a breadth-first search in which a state is pruned when it is not the first state in the search to make true some subset of i atoms. The empirical results over 54 games suggest that the performance of IW with the k parameter fixed to 1, i.e., IW(1), is at the level of the state of the art represented by UCT. A sim-ple best-first variation of IW that combines exploration and exploitation proves to be very competitive as well.

    Original languageEnglish
    Title of host publicationLearning for General Competency in Video Games - Papers Presented at the 29th AAAI Conference on Artificial Intelligence, Technical Report
    PublisherAI Access Foundation
    Pages21-28
    Number of pages8
    ISBN (Electronic)9781577357216
    Publication statusPublished - 2015
    Event29th AAAI Conference on Artificial Intelligence, AAAI 2015 - Austin, United States
    Duration: 25 Jan 201530 Jan 2015

    Publication series

    NameAAAI Workshop - Technical Report
    VolumeWS-15-10

    Conference

    Conference29th AAAI Conference on Artificial Intelligence, AAAI 2015
    Country/TerritoryUnited States
    CityAustin
    Period25/01/1530/01/15

    Fingerprint

    Dive into the research topics of 'Classical planning algorithms on the atari video games'. Together they form a unique fingerprint.

    Cite this