Modeling uncertainty and its implications to sophisticated control in taems agents. Autonomous Agents and Multi-Agent Systems

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 TÆMS 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 TÆMS computational task models analyzed by the scheduler and the incorporation of uncertainty in the scheduling process. As we show, the use of uncertainty in TÆMS 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 th