A context aware model for autonomous agent stochastic planning

2019-02-01
Markov Decision Processes (MDPs) are not able to make use of domain information effectively due to their representational limitations. The lacking of elements which enable the models be aware of context, leads to unstructured representation of that problem such as raw probability matrices or lists. This causes these tools significantly less efficient at determining a useful policy as the state space of a task grows, which is the case for more realistic problems having localized dependencies between states and actions. In this paper, we present a new state machine, called Context-Aware Markov Decision Process (CA-MDP) based on MDP for the purpose of representing Markovian sequential decision making problems in a more structured manner. CA-MDP changes and augments MDP facilities by integrating causal relationships between actions and states thereby enabling structural, hence compact if possible, representation of the tasks. To show the expressive power of CA-MDP, we give the theoretical bounds for complexity of conversion between MDP and CA-MDP to demonstrate the expressive power of CA-MDP. Next, to generate an optimal policy from CA-MDP encoding by exploiting those newly defined facilities, we devised a new solver algorithm based on value iteration (VI), called Context-Aware Value Iteration (CA-VI). Although regular dynamic programming (DP) based algorithms is successful at effectively determining optimal policies, they do not scale well with respect to state-action space, making both the MDP encoding and related solver mechanism practically unusable for real-life problems. Our solver algorithm gets the power of overcoming the scalability problem by integrating the structural information provided in CA-MDP. First, we give theoretical analysis of CA-VI by examining the expected number of Bellman updates being performed on arbitrary tasks. Finally, we present our conducted experiments on numerous problems, with important remarks and discussions on certain aspects of CA-VI and CA-MDP, to justify our theoretical analyses empirically and to assess the real performance of CA-VI with CA-MDP formulation by analysing the execution time by checking how close it gets to the practical minimum runtime bound with respect to VI performance with MDP encoding of the same task.
ROBOTICS AND AUTONOMOUS SYSTEMS

Suggestions

A dynamic programming algorithm for tree-like weighted set packing problem
Gulek, Mehmet; Toroslu, İsmail Hakkı (Elsevier BV, 2010-10-15)
In hierarchical organizations, hierarchical structures naturally correspond to nested sets. That is, we have a collection of sets such that for any two sets, either one of them is a subset of the other, or they are disjoint. In other words, a nested set system forms a hierarchy in the form of a tree structure. The task assignment problem on such hierarchical organizations is a real life problem. In this paper, we introduce the tree-like weighted set packing problem, which is a weighted set packing problem r...
A finite field framework for modeling, analysis and control of finite state automata
Reger, Johann; Schmidt, Klaus Verner (Informa UK Limited, 2004-09-01)
In this paper, we address the modeling, analysis and control of finite state automata, which represent a standard class of discrete event systems. As opposed to graph theoretical methods, we consider an algebraic framework that resides on the finite field F-2 which is defined on a set of two elements with the operations addition and multiplication, both carried out modulo 2. The key characteristic of the model is its functional completeness in the sense that it is capable of describing most of the finite st...
A knowledge based product line for semantic modeling of web service families
Orhan, Umut; Doğru, Ali Hikmet; Department of Computer Engineering (2008)
Some mechanisms to enable an effective transition from domain models to web service descriptions are developed. The introduced domain modeling support provides verification and correction on the customization part. An automated mapping mechanism from the domain model to web service ontologies is also developed. The proposed approach is based on Feature-Oriented Domain Analysis (FODA), Semantic Web technologies and ebXML Business Process Specification Schema (ebBP). Major contributions of this work are the c...
A Framework for qualitative assessment of domain specific languages
Kahraman, Gökhan; Bilgen, Semih; Department of Electrical and Electronics Engineering (2013)
Domain Specific Languages (DSLs) have been proposed in the literature with the aim of providing a wide range of advantages such as better productivity and quality for stakeholders involved with many aspects of software development. The objective of this study consists of supporting the improvement of DSL maturity by providing an A Framework for Qualitative Assessment of DSLs(FQAD). A formal approach is proposed for the assessment of DSLs. Metrics for DSL success measurement and the parameters that affect th...
An access structure for similarity-based fuzzy databases
Yazıcı, Adnan (Elsevier BV, 1999-04-01)
A significant effort has been made in representing imprecise information in database models by using fuzzy set theory. However, the research directed toward access structures to handle fuzzy querying effectively is still at an immature stage. Fuzzy querying involves more complex processing than the ordinary querying does. Additionally, a larger number of tuples are possibly selected by fuzzy conditions in comparison to the crisp ones. It is obvious that the need for fast response time becomes very important...
Citation Formats
Ö. Ekmekci and F. Polat, “A context aware model for autonomous agent stochastic planning,” ROBOTICS AND AUTONOMOUS SYSTEMS, pp. 137–153, 2019, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/39811.