Publication - Modeling Uncertainty and its Implications to Sophisticated Control in TAEMS Agents

Authors: Wagner, Thomas; Raja, Anita; Lesser, Victor
Title: Modeling Uncertainty and its Implications to Sophisticated Control in TAEMS Agents
Abstract: Open environments are characterized by their uncertainty and non-determinism. Agents need to adapt their task processing to available resources, deadlines, the goal criteria specified by the clients as well their current problem solving context in order to survive in these environments. If there were no resource constraints, then an optimal Markov Decision Process based policy would obviously be the best way for complex problem solving agents to make scheduling decisions. However in many agent systems, these scheduling decisions have to be made on-line or in soft real-time, making the off-line policy computationally infeasible in open environments. The hybrid planner/scheduler used to control Task Analysis, Environment Modeling, and Simulation (teams) agents is the Design-to-Criteria (DTC) agent scheduler. Design-to-Criteria scheduling is the soft real-time process of custom building a plan/schedule to meet an agentís current objectives which are expressed as dynamic goal criteria (including real-time deadlines), using task models that describe alternate ways to achieve tasks and subtasks. Recent advances in Design-to-Criteria control include the addition of uncertainty to the teams computational task models analyzed by the scheduler and the incorporation of uncertainty in the scheduling process. As we show, the use of uncertainty in teams and Design-to-Criteria enables agents to make better control decisions in uncertain environments. Design-to-Criteria uses a heuristic approach for on-line scheduling of medium granularity tasks.It approximates the analysis used to generate an optimal policy by heuristically reasoning about the implications of uncertainty in task execution. The addition of uncertainty has also spawned a post-scheduling contingency analysis step for situations in which an agent must produce a result by a given deadline (deadline critical situations) and where the added computational cost is worth the expense. We describe the uncertainty representation in teams and how it improves task models and the scheduling process, and provide empirical examples of reasoning about uncertainty in action. We also evaluate the performance of our heuristic-based approach to agent control using the performance of the policy generated by an optimal controller as the benchmark.
Keywords: Contingency, Control, MDP, Uncertainty
Publication: Autonomous Agents and Multi-Agent Systems, Vol: 13, Num: 3, pp. 235 - 292
Publisher: Springer: Netherlands
Date: November 2006
Sources: Citeseer: /Documents/Wagner/Wagner_JAAMAS06.pdf
HTML: http://www.springerlink.com/link.asp?id=m132562q4865522g
HTML: http://dx.doi.org/10.1007/s10458-006-7669-2
Notes: On-line version available April 2006.
Reference: Wagner, Thomas; Raja, Anita; Lesser, Victor. Modeling Uncertainty and its Implications to Sophisticated Control in TAEMS Agents. Autonomous Agents and Multi-Agent Systems, Volume 13, Number 3, Springer: Netherlands, pp. 235-292. November 2006. On-line version available April 2006.
bibtex:
@article{Wagner-425,
  author    = "Thomas Wagner and Anita Raja and Victor Lesser",
  title     = "{Modeling Uncertainty and its Implications to
               Sophisticated Control in TAEMS Agents}",
  journal   = "Autonomous Agents and Multi-Agent Systems",
  volume    = "13",
  number    = "3",
  publisher = "Springer: Netherlands",
  pages     = "235-292",
  month     = "November",
  year      = "2006",
  url       = "http://mas.cs.umass.edu/paper/425",
}