Graduate studies at Western
Journal of Logic, Language and Information 18 (1):55-77 (2009)
|Abstract||We study the logic of strategic ability of coalitions of agents with bounded memory by introducing Alternating-time Temporal Logic with Bounded Memory (ATLBM), a variant of Alternating-time Temporal Logic (ATL). ATLBM accounts for two main consequences of the assumption that agents have bounded memory. First, an agent can only remember a strategy that specifies actions in a bounded number of different circumstances. While the ATL-formula means that coalition C has a joint strategy which will make φ true forever, the ATLBM-formula means that C has a joint strategy which for each agent in C specifies what to do in no more than n different circumstances and which will make φ true forever. Second, an agent has bounded recall—a strategy can only take the last m states of the system into account. We use the logic to study the interaction between strategic ability, bounded number of decisions, bounded recall and incomplete information. We discuss the logical properties and expressiveness of ATLBM, and its relationship to ATL. We show that ATLBM can express properties of strategic ability under bounded memory which cannot be expressed in ATL.|
|Keywords||Alternatingtime temporal logic Multi-agent systems Resource-bounded reasoning Strategic ability|
|Categories||categorize this paper)|
|Through your library||Configure|
Similar books and articles
Michael Fisher & Chiara Ghidini (2009). Exploring the Future with Resource-Bounded Agents. Journal of Logic, Language and Information 18 (1):3-21.
Natasha Alechina & Brian Logan (2009). A Logic of Situated Resource-Bounded Agents. Journal of Logic, Language and Information 18 (1):79-95.
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.
Hans K. Hvide (1999). Bounds to Memory Loss. Theory and Decision 46 (1):1-21.
Domenico Zambella (1996). Notes on Polynomially Bounded Arithmetic. Journal of Symbolic Logic 61 (3):942-966.
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.
Natasha Alechina, Brian Logan, Hoang Nga Nguyen & Abdur Rakib (2009). Verifying Time, Memory and Communication Bounds in Systems of Reasoning Agents. Synthese 169 (2):385 - 403.
Natasha Alechina & Brian Logan (2010). Belief Ascription Under Bounded Resources. Synthese 173 (2):179 - 197.
Thomas Ågotnes (2006). Action and Knowledge in Alternating-Time Temporal Logic. Synthese 149 (2):375 - 407.
Added to index2009-01-28
Total downloads17 ( #78,355 of 754,681 )
Recent downloads (6 months)0
How can I increase my downloads?