International Journal of Artificial Intelligent and Expert Systems (IJAE) Volume 1, Issue 3

---

International Journal of
Artificial Intelligent and Expert
Systems (IJAE)
Volume 1, Issue 3, 2010
Edited By
Computer Science Journals
www.cscjournals.org

---

Editor in Chief Dr. Bekir Karlik
International Journal of Artificial Intelligent
and Expert Systems (IJAE)
Book: 2010 Volume 1, Issue 3
Publishing Date: 30-10-2010
Proceedings
ISSN (Online): 2180-124X
This work is subjected to copyright. All rights are reserved whether the whole or
part of the material is concerned, specifically the rights of translation, reprinting,
re-use of illusions, recitation, broadcasting, reproduction on microfilms or in any
other way, and storage in data banks. Duplication of this publication of parts
thereof is permitted only under the provision of the copyright law 1965, in its
current version, and permission of use must always be obtained from CSC
Publishers. Violations are liable to prosecution under the copyright law.
IJAE Journal is a part of CSC Publishers
http://www.cscjournals.org
© IJAE Journal
Published in Malaysia
Typesetting: Camera-ready by author, data conversation by CSC Publishing
Services – CSC Journals, Malaysia
CSC Publishers

---

Editorial Preface
The International Journal of Artificial Intelligence and Expert Systems
(IJAE) is an effective medium for interchange of high quality theoretical and
applied research in Artificial Intelligence and Expert Systems domain from
theoretical research to application development. This is the third issue of
volume first of IJAE. The Journal is published bi-monthly, with papers being
peer reviewed to high international standards. IJAE emphasizes on efficient
and effective Artificial Intelligence, and provides a central for a deeper
understanding in the discipline by encouraging the quantitative comparison
and performance evaluation of the emerging components of Expert Systems.
IJAE comprehensively cover the system, processing and application aspects
of Artificial Intelligence. Some of the important topics are AI for Service
Engineering and Automated Reasoning, Evolutionary and Swarm Algorithms
and Expert System Development Stages, Fuzzy Sets and logic and
Knowledge-Based Systems, Problem solving Methods Self-Healing and
Autonomous Systems etc.
IJAE give an opportunity to scientists, researchers, and vendors from
different disciplines of Artificial Intelligence to share the ideas, identify
problems, investigate relevant issues, share common interests, explore new
approaches, and initiate possible collaborative research and system
development. This journal is helpful for the researchers and R&D engineers,
scientists all those persons who are involve in Artificial Intelligence and
Expert Systems in any shape.
Highly professional scholars give their efforts, valuable time, expertise and
motivation to IJAE as Editorial board members. All submissions are evaluated
by the International Editorial Board. The International Editorial Board ensures
that significant developments in image processing from around the world are
reflected in the IJAE publications.
IJAE editors understand that how much it is important for authors and
researchers to have their work published with a minimum delay after
submission of their papers. They also strongly believe that the direct
communication between the editors and authors are important for the
welfare, quality and wellbeing of the Journal and its readers. Therefore, all
activities from paper submission to paper publication are controlled through
electronic systems that include electronic submission, editorial panel and
review system that ensures rapid decision with least delays in the publication
processes.
To build its international reputation, we are disseminating the publication
information through Google Books, Google Scholar, Directory of Open Access
Journals (DOAJ), Open J Gate, ScientificCommons, Docstoc and many more.
Our International Editors are working on establishing ISI listing and a good

---

impact factor for IJAE. We would like to remind you that the success of our
journal depends directly on the number of quality articles submitted for
review. Accordingly, we would like to request your participation by
submitting quality manuscripts for review and encouraging your colleagues to
submit quality manuscripts for review. One of the great benefits we can
provide to our prospective authors is the mentoring nature of our review
process. IJAE provides authors with high quality, helpful reviews that are
shaped to assist authors in improving their manuscripts.
Editorial Board Members
International Journal of Artificial Intelligence and Expert Systems (IJAE)

---

Editorial Board
Editor-in-Chief (EiC)
Dr. Bekir Karlik
Mevlana University (Turkey)
Associate Editor-in-Chief (AEiC)
Assistant Professor. Tossapon Boongoen
Royal Thai Air Force Academy (Thailand)
Editorial Board Members (EBMs)
Professor. Yevgeniy Bodyanskiy
Kharkiv National University of Radio Electronics (Ukraine)
Assistant Professor. Bilal Alatas
Firat University (Turkey)

---

Table of Content
Volume 1, Issue 3, October 2010
Pages
54 - 64
Planning in Markov Stochastic Task Domains
Yong (Yates) Lin, Fillia Makedon
65 - 74 A Design of Fuzzy Controller for Autonomous Navigation of
Unmanned Vehicle
Vinod Kapse, Bhavana Jharia, S. S. Thakur
International Journal of Artificial Intelligence and Expert Systems (IJAE) Volume (1) Issue (3)

---

Yong (Yates) Lin & Fillia Makedon
Planning in Markov Stochastic Task Domains


Yong (Yates) Lin



ylin@uta.edu
Computer Science & Engineering
University of Texas at Arlington
Arlington, TX 76019, USA

Fillia Makedon





makedon@uta.edu
Computer Science & Engineering
University of Texas at Arlington
Arlington, TX 76019, USA

Abstract

In decision theoretic planning, a challenge for Markov decision processes (MDPs)
and partially observable Markov decision processes (POMDPs) is, many problem
domains contain big state spaces and complex tasks, which will result in poor
solution performance. We develop a task analysis and modeling (TAM) approach,
in which the (PO)MDP model is separated into a task view and an action view. In
the task view, TAM models the problem domain using a task equivalence model,
with task-dependent abstract states and observations. We provide a learning
algorithm to obtain the parameter values of task equivalence models. We present
three typical examples to explain the TAM approach. Experimental results
indicate our approach can greatly improve the computational capacity of task
planning in Markov stochastic domains.

Keywords: Markov decision processes, POMDP, task planning, uncertainty, decision-making.


1. INTRODUCTION
We often refer to a specific process with goals or termination conditions as a task. Tasks are
highly related to situation assessment, decision making, planning and execution. For each task,
we achieve the goals by a series of actions. Complex task contains not only different kinds of
actions, but also various internal relationships, such as causality, hierarchy, etc.

Existing problems of (PO)MDPs have often been constrained in small state spaces and simple
tasks. For example, Hallway is a task in which a robot tries to reach a target in a 15-grids
apartment [11]. From the perspective of task, this process has only a single goal. The difficulties
come from noisy observations by imprecise sensors equipped on the robot, instead of task.

Although (PO)MDPs have been accepted as successful mathematical approaches to model
planning and controlling processes, without an efficient solution for big state spaces and complex
tasks, we cannot apply these models on more general problems in the real world. In a simple task
of grasping an object, the number of states reaches |S| =1253 [8]. If the task domain becomes
complex, it will be even harder to utilize these models. Suppose an agent aims to build a house,
there will be thousands of tasks, with different configurations of states, actions and observations.
It is hardly to rely simply on (PO)MDPs to solve this problem domain. Compared to other task
planning approaches, such as STRIPS or Hierarchical Task Network [10], (PO)MDPs consider
International Journal of Artificial Intelligence and Expert Systems (IJAE), Volume (1): Issue (3)
54

---

Yong (Yates) Lin & Fillia Makedon
the optimization for every step of the planning. Therefore, (PO)MDPs are more suitable for
planning and controlling problems of intelligent agents. However, for task management, the
(PO)MDP framework is not as powerful as Hierarchical Task Network (HTN) planning [3]. HTN is
designed to handle problems with many tasks. Primitive tasks can be executed directly, and non-
primitive tasks will be decomposed into subtasks, until everyone becomes a primitive task. This
idea is adopted in the hierarchical partially observable Markov decision processes (HPOMDPs)
[12]. Actions in HPOMDPs are arranged in a tree. A task will be decomposed into subtasks. Each
subtask has an action set containing primitive actions and/or abstract actions. In fact, a
hierarchical framework for (PO)MDPs is an approach that builds up a hierarchical structure to
invoke the abstract action sub-functions. Although inherited the merits of task management from
HTN, it does not specially address the solving of the big state space problem.

Another solution considers multiple tasks as a merging problem using multiple simultaneous
MDPs [15]. This solution does not specially consider the characteristic of different tasks, and it
limits the problem domains to be MDPs.

To improve the computational capacity of complex tasks planning, we develop a task analysis
and modeling approach. We decompose the model into a task view and an action view. This
enables us to strip out the details, such that we can focus on the task view. After a learning
process from the action view, the task view becomes an independent task equivalence model,
with task-dependent abstract states and observations. If the problem domain is MDP, we have
already solved it by the task view learning algorithm. If it is POMDP, we can solve it using any
existing POMDP algorithms, without considering the hierarchical relationship anymore. We apply
the TAM approach on existing MDP and POMDP problems. Experimental results indicate the
TAM approach brings us closer to the optimum solution of multi-task planning and controlling
problems.

This paper is organized as follows. We begin by a brief review of MDPs and POMDPs. Then we
discuss how to utilize the TAM method on (PO)MDP problems. Three typical examples from
MDPs and POMDPs are presented in this part, to explain the design of task equivalence models.
In the following section, we present a solution based on knowledge acquisition and model-
learning for the task equivalence models. We provide our experimental results for the comparison
of the task equivalence model and the original POMDP model. Finally, we briefly introduce some
related work and conclude the paper.

2. BACKGROUND
A Markov decision process (MDP) is a tuple
, where the S is a set of
states, the A is a set of actions, the T(s, a, s0) is the transition probability from state s to s0 using
action a, R(s, a) is the reward when executing action a in state s, and is the discount factor.
The optimal situation-action mapping for the tth step, denoted as
, can be reached by the
optimal (t-1)-step value function
:
.

A POMDP models an agent action in uncertainty world. At each time step, the agent needs to
make a decision based on the historical information from previous executions. A policy is a
function of action selection under stochastic state transitions and noisy observations. A POMDP
can be represented as
, where
is a finite set of states,
is
a set of actions,
is a set of observations. In each time step, the agent lies in a state
.
After taking an action
, the agent goes into a new state s0. The transition is a conditional
probability function T(s, a, s’) = p(s’|s, a), which presents the probability the agent lies in s’, after
taking action a in state s. The agent makes an observation
to gather information. This
International Journal of Artificial Intelligence and Expert Systems (IJAE), Volume (1): Issue (3)
55

---

Yong (Yates) Lin & Fillia Makedon
can be modeled as a conditional probability (s, a, o) = p(o|s, a).

When belief state is taken into consideration, the original partially observable POMDP model
changes to a fully observable MDP model, denoted as
. Here,
the B is a set of belief states, i.e. belief space. The
is a probability the agent
changes from b to b0 after taking action a. The
is the reward for belief
state b. The b0 is an initial belief state.

The POMDP framework is used as a control model of an agent. In a control problem, utility is
defined as a real-valued reward to determine the action of an agent in each time step, denoted as
R(s, a), which is a function of state s and action a. The optimal action selection becomes a
problem to find a sequence of actions a1..t, in order to maximize the expected sum of rewards
. In this process, what we concern is the controlling effect, achieved from the
relative relationship of the values. When we use a discount factor , the relative relationship
remains unchanged, but the values can converge to a fixed number. When states are not fully
observable, the goal is changed to maximize expected reward for each belief state. The nth
horizon value function can be built from previous value nth using a backup operator H, i.e. V = HV’.
The value function is formulated as the following Bellman equation
.

Here, b’ is the next step belief state,
,
where is a normalizing constant.

When optimized exactly, this value function is always piece-wise linear and convex in the belief
space.

3. EQUIVALENCE MODELS ON TASK DOMAINS
Tasks serve as basic units of everyday activities of humans and intelligent agents. A task-
oriented agent builds its policies on the context of different tasks. Generally speaking, a task
contains a series of actions and some certain relationships, with an initial state s0, where it starts
from, and one or multiple absorbing states sg (goals and/or termination states), where the task
ends in. (RockSample [16] is a typical example using termination state instead of goals.
Theoretically, infinite tasks may not have goal or termination state, we can simply set sg = null).
From this notion, every (PO)MDP problem can be described as a task (For POMDP, the initial
state becomes b0, and absorbing states become bg). To improve the computational capacity of
task planning, we develop a task analysis and modeling (TAM) approach.

3.1
Task Analysis
Due to the size of state space, and the complex relationships among task states, it is hard to
analyze tasks. Therefore, we separate a task, which is a tuple M, into a task view and an action
view. The task view, denoted as
, reflects how we define an abstract model for the original task.
Actions used in a task view is defined in an action view, denoted as
. It contains all of the
actions in the original task. Before further discussion about the task view and the action view, let
us first go over some terms used in this framework.

An action a is a single or a set of operational instructions an agent takes to finish a primitive task.
A Markov decision model is a framework to decide which action should be taken in each state. If
an action defined in a Markov stochastic domain is used by a primitive task, we assume it to be a
primitive action.
International Journal of Artificial Intelligence and Expert Systems (IJAE), Volume (1): Issue (3)
56

---