Other Agents' Actions as Asynchronous Events
Kurt D. Krebsbach · 2006
An individual planning agent does not generally have sufficient computational resources at its disposal to pro-duce an optimal plan in a complex domain, as delibera-tion itself requires and consumes scarce resources. This problem is further exacerbated in a distributed plan-ning context in which multiple, heterogeneous agents must expend a portion of their resource allotment on communication, negotiation, and shared planning ac-tivities with other cooperative agents. Because other agents can have different temporal grain sizes, plan-ning horizons, deadlines, and access to distinct local information, the delays associated with local delibera-tion and, in turn, shared negotiation are asynchronous, unpredictable, and widely variable. We address this problem using a principled, decision-theoretic approach based on recent advances in Gen-eralized Semi-Markov Decision Processes (GSMDPs). In particular, we use GSMDPs to model agents who develop a continuous-time deliberation policy offline which can then be consulted to dynamically select both deliberation-level and domain-level actions at plan ex-ecution time. This scheme allows individual agents to model other cooperative agents ’ actions essentially as asynchronous events, e.g., that might or might not ful-fill a request (uncertain effect) after a stochastically-determined delay (uncertain event duration). With this approach, the decision-theoretic planner for the individ-ual agent can make near-optimal execution-time deci-sions that trade off the risks and opportunities associ-ated with their own actions, other agents ’ actions, and asynchronous external threats.