Planning with Time Limits in BDI Agent Programming LanguagesLavindra de SilvaRMIT University,Melbourne,Australia ldesilva@cs.rmit.edu.au Anthony DekkerDSTO∗,Canberra,Australiadekker@ACM.orgJames HarlandRMIT University,Melbourne,Australiajah@cs.rmit.edu.auAbstractThis paper provides a theoretical basis for performing time limited planning within Belief-Desire-Intention (BDI)agents.The BDI agent architecture is recog-nised as one of the most popular architectures for developing agents for complex and dynamic environ-ments,in addition to which they have a strong the-oretical foundation.Recent work has extended a BDI agent specification language to include HTN-style planning as a built-in feature.However,the ex-tended semantics assume that agents have an unlim-ited amount of time available to perform planning, which is often not the case in many dynamic real world environments.We extend previous research by using ideas from anytime algorithms,and allow pro-grammer control over the amount of time the agent spends on planning.We show that the resulting in-tegrated agent specification language has advantages over regular BDI agent reasoning.Keywords:BDI Agents,Operational Semantics,Time Limited Planning1IntroductionAn Intelligent Agent is piece of software that is (Jennings,Sycara&Wooldridge1998):situated in an environment,capable of autonomous behaviour, i.e.with little or no intervention from humans,and flexible.Flexibility means the agent is:responsive to the environment(i.e.able to perceive and re-spond to changes in a timely manner),proactive(i.e. able to exhibit goal directed behaviour),and social (i.e.able to interact with other agents and humans). Intelligent agents are used in numerous real world applications such as Unmanned Autonomous Vehi-cles(UAV)(Karim&Heinze2005)and autonomous spacecraft control(Chien,Knight,Stechert,Sher-wood&Rabideau n.d.).The BDI(Belief-Desire-Intention)architecture, based on Bratman’s theory of practical reasoning (Bratman1987)and Dennett’s theory of intentional systems(Dennett1987),is a popular and well stud-ied model for intelligent agents situated in com-plex and dynamic environments.Beliefs represent an agent’s knowledge of its environment,Desires represent an agent’s goals or its desired outcomes, and an Intention is a chosen desire that the agent commits to.The purpose of the BDI architecture ∗Defense Science and Technology OrganisationCopyright c 2007,Australian Computer Society,Inc.This pa-per appeared at Computing:The Australasian Theory Sym-posium(CATS2007),Ballarat,Australia.Conferences in Re-search and Practice in Information Technology(CRPIT),Vol.65.Joachim Gudmundsson and Barry Jay,Eds.Reproduction for academic,not-for profit purposes permitted provided this text is included.is to make agents capable of behaving in a more human-like manner.There are numerous BDI agent programming and specification languages such as Prs(Ingrand,Georgeff&Rao1992),AgentSpeak (Rao1996),3APL(Hindriks,de Boer,van der Hoek &Meyer1999),Jack(Busetta,R¨o nnquist,Hodgson &Lucas1999)and Can(Winikoff,Padgham,Har-land&Thangarajah2002).BDI systems execute as they reason and are ro-bust in handling failure,therefore well suited for com-plex and dynamic environments requiring real-time reasoning capabilities.However,reasoning for longer durations before acting is also advantageous in cer-tain situations where time is less critical,and with the recent advances in planning technology,planning or lookahead within the BDI architecture has become feasible.In(Sardina,de Silva&Padgham2006),Hier-archical Task Network(HTN)style planning(Erol, Hendler&Nau1994)capabilities were integrated into the Can BDI specification language introduced in (Winikoffet al.2002).The integration involved(1) extending the Can operational semantics with plan-ning capabilities to form CanPlan;(2)substantially improving and simplifying the Can operational se-mantics;and(3)exploring the theoretical properties of the new CanPlan language.CanPlan is a goodfirst step towards formalising the type of planning that is appropriate for the BDI architecture.However,a notable limitation in the semantics is in not having control over the amount of time to be spent on planning–CanPlan will attempt tofind a complete solution for a goal,before executing thefirst action.Control over the planning duration is necessary in many domains,as it is often the case that agents only have(or should only spend)a limited amount of time for(on)planning.Planning with time limits is important when solving real-time problems in a moderately fast-changing world(Korf1990,Dean,Kaelbling,Kirman &Nicholson1993b).In such situations,performing a relatively poor action in time may be preferable to performing a planned action which is too late.Plan-ning with time limits can be achieved by giving the planner an explicit time limit,and falling back on BDI-style reaction if necessary.Planning with time limits is also useful in agent-based modelling and simulation of real human organ-isations.Under extreme time pressure,human beings react by curtailing planning which cannot provide a solution in time(Newell&Simon1972,Gigerenzer &Selten2002).The CAVALIER-NPA framework (Dekker&de Silva2006)investigates the impact of planning time,communications delays,and workload sharing in military organisations through modelling with BDI agents augmented by time-limited planning.Therefore,it is important that work with time-limited planning of this kind be placed on a solid