On composition of bounded-recall plans

摘要

The article studies the ability of agents with bounded memory to execute consecutive composition of plans. It gives an upper limit on the amount of memory required to execute the composed plans and shows that the limit cannot be improved. Furthermore, the article shows that there are, essentially, no other universal properties of plans for bounded-recall agents expressible through the relation “there is a plan for an agent with a given memory size to navigate from one given set of states to another”.