Graduate studies at Western
Synthese 169 (2):385 - 403 (2009)
|Abstract||We present a framework for verifying systems composed of heterogeneous reasoning agents, in which each agent may have differing knowledge and inferential capabilities, and where the resources each agent is prepared to commit to a goal (time, memory and communication bandwidth) are bounded. The framework allows us to investigate, for example, whether a goal can be achieved if a particular agent, perhaps possessing key information or inferential capabilities, is unable (or unwilling) to contribute more than a given portion of its available computational resources or bandwidth to the problem. We present a novel temporal epistemic logic, BMCL-CTL , which allows us to describe a set of reasoning agents with bounds on time, memory and the number of messages they can exchange. The bounds on memory and communication are expressed as axioms in the logic. As an example, we show how to axiomatise a system of agents which reason using resolution and prove that the resulting logic is sound and complete. We then show how to encode a simple system of reasoning agents specified in BMCL-CTL in the description language of the Mocha model checker (Alur et al., Proceedings of the tenth international conference on computer-aided verification (CAV) , 1998), and verify that the agents can achieve a goal only if they are prepared to commit certain time, memory and communication resources.|
|Keywords||Distributed reasoning Resource bounds Epistemic logic|
|Categories||categorize this paper)|
|Through your library||Configure|
Similar books and articles
Hans K. Hvide (1999). Bounds to Memory Loss. Theory and Decision 46 (1):1-21.
Andreas Herzig & Emiliano Lorini (2010). A Dynamic Logic of Agency I: Stit, Capabilities and Powers. [REVIEW] Journal of Logic, Language and Information 19 (1):89-121.
Wiebe van Der Hoek & Michael Wooldridge (2003). Cooperation, Knowledge, and Time: Alternating-Time Temporal Epistemic Logic and Its Applications. Studia Logica 75 (1):125 - 157.
Thomas Ågotnes & Dirk Walther (2009). A Logic of Strategic Ability Under Bounded Memory. Journal of Logic, Language and Information 18 (1):55-77.
Wiebe van der Hoek & Michael Wooldridge (2003). Cooperation, Knowledge, and Time: Alternating-Time Temporal Epistemic Logic and its Applications. Studia Logica 75 (1):125-157.
Michał Walicki, Marc Bezem & Wojtek Szajnkenig (2009). Developing Bounded Reasoning. Journal of Logic, Language and Information 18 (1):97-129.
Brian Logan, Mark Jago & Natasha Alechina (2006). Modelling Communicating Agents in Timed Reasoning Logics. In U. Endriss & M. Baldoni (eds.), Declarative Agent Languages and Technologies 4. Springer.
Natasha Alechina & Brian Logan (2010). Belief Ascription Under Bounded Resources. Synthese 173 (2):179 - 197.
Natasha Alechina, Piergiorgio Bertoli, Chiara Ghidini, Mark Jago, Brian Logan & Luciano Serafini (2007). Verifying Space and Time Requirements for Resource-Bounded Agents. In A. Lomuscio & S. Edelkamp (eds.), Model Checking and Artificial Intelligence. Springer.
Added to index2009-05-02
Total downloads18 ( #74,836 of 754,747 )
Recent downloads (6 months)1 ( #63,372 of 754,747 )
How can I increase my downloads?