Adaptation-based programming Public Deposited

http://ir.library.oregonstate.edu/concern/graduate_thesis_or_dissertations/3j333488d

Descriptions

Attribute NameValues
Creator
Abstract or Summary
  • Partial programming is a field of study where users specify an outline or skeleton of a program, but leave various parts undefined. The undefined parts are then completed by an external mechanism to form a complete program. Adaptation-Based Programming (ABP) is a method of partial programming that utilizes techniques from the field of reinforcement learning (RL), a subfield of machine learning, to find good completions of those partial programs. An ABP user writes a partial program in some host programming language. At various points where the programmer is uncertain of the best course of action, they include choices that non-deterministically select amongst several options. Additionally, users indicate program success through a reward construct somewhere in their program. The resulting non-deterministic program is completed by treating it as an equivalent RL problem and solving the problem with techniques from that field. Over repeated executions, the RL algorithms within the ABP system will learn to select choices at various points that maximize the reward received. This thesis explores various aspects of ABP such as the semantics of different implementations, including different design trade-offs encountered with each approach. The goal of all approaches is to present a model for programs that adapt to their environment based on the points of uncertainty within the program that the programmer has indicated. The first approach presented in this work is an implementation of ABP as a domain-specific language embedded within a functional language. This language provides constructs for common patterns and situations that arise in adaptive programs. This language proves to be compositional and to foster rapid experimentation with different adaptation methods (e.g. learning algorithms). A second approach presents an implementation of ABP as an object-oriented library that models adaptive programs as formal systems from the field of RL called Markov Decision Processes (MDPs). This approach abstracts away many of the details of the learning algorithm from the casual user and uses a fixed learning algorithm to control the program adaptation rather than allowing it to vary. This abstraction results in an easier-to-use library, but limits the scenarios that ABP can effectively be used in. Moreover, treating adaptive programs as MDPs leads to some unintuitive situations where seemingly reasonably programs fail to adapt efficiently. This work addresses this problem with algorithms that analyze the adaptive program's structure and data flow to boost the rate at which these problematic adaptive programs learn thus increasing the number of problems that ABP can effectively be used to solve.
Resource Type
Date Available
Date Copyright
Date Issued
Degree Level
Degree Name
Degree Field
Degree Grantor
Commencement Year
Advisor
Committee Member
Academic Affiliation
Non-Academic Affiliation
Keyword
Subject
Rights Statement
Peer Reviewed
Language
Replaces
Additional Information
  • description.provenance : Submitted by Timothy Bauer (bauertim@onid.orst.edu) on 2013-02-27T22:40:43Z No. of bitstreams: 3 license_rdf: 19965 bytes, checksum: 225316337756db2af069c3edfe03a49f (MD5) license_text: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) BauerTimR2013.pdf: 1440071 bytes, checksum: 7e28bd84420df7c42c349519e1a00859 (MD5)
  • description.provenance : Submitted by Timothy Bauer (bauertim@onid.orst.edu) on 2013-03-05T19:10:38Z No. of bitstreams: 3 license_rdf: 19965 bytes, checksum: 225316337756db2af069c3edfe03a49f (MD5) license_text: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) BauerTimR2013.pdf: 1520976 bytes, checksum: 940480a119bdd2c85ec96a3eea784d11 (MD5)
  • description.provenance : Made available in DSpace on 2013-03-07T19:14:29Z (GMT). No. of bitstreams: 3 license_rdf: 19965 bytes, checksum: 225316337756db2af069c3edfe03a49f (MD5) license_text: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) BauerTimR2013.pdf: 1520976 bytes, checksum: 940480a119bdd2c85ec96a3eea784d11 (MD5) Previous issue date: 2013-01-31
  • description.provenance : Rejected by Julie Kurtz(julie.kurtz@oregonstate.edu), reason: Rejecting per student. on 2013-03-01T22:12:37Z (GMT)
  • description.provenance : Approved for entry into archive by Laura Wilson(laura.wilson@oregonstate.edu) on 2013-03-07T19:14:29Z (GMT) No. of bitstreams: 3 license_rdf: 19965 bytes, checksum: 225316337756db2af069c3edfe03a49f (MD5) license_text: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) BauerTimR2013.pdf: 1520976 bytes, checksum: 940480a119bdd2c85ec96a3eea784d11 (MD5)
  • description.provenance : Approved for entry into archive by Julie Kurtz(julie.kurtz@oregonstate.edu) on 2013-03-07T17:57:12Z (GMT) No. of bitstreams: 3 license_rdf: 19965 bytes, checksum: 225316337756db2af069c3edfe03a49f (MD5) license_text: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) BauerTimR2013.pdf: 1520976 bytes, checksum: 940480a119bdd2c85ec96a3eea784d11 (MD5)

Relationships

Parents:

This work has no parents.

Last modified

Downloadable Content

Download PDF

Items