foundations of computational agents
Figure 1.6 summarizes the dimensions of complexity. Unfortunately, we cannot study these dimensions entirely independently because they interact in complex ways. Here we give some examples of the interactions.
|Modularity||flat, modular, hierarchical|
|Planning horizon||non-planning, finite stage,|
|indefinite stage, infinite stage|
|Representation||states, features, relations|
|Computational limits||perfect rationality, bounded rationality|
|Learning||knowledge is given, knowledge is learned|
|Sensing uncertainty||fully observable, partially observable|
|Effect uncertainty||deterministic, stochastic|
|Preference||goals, complex preferences|
|Number of agents||single agent, multiple agents|
The representation dimension interacts with the modularity dimension in that some modules in a hierarchy may be simple enough to reason in terms of a finite set of states, whereas other levels of abstraction may require reasoning about individuals and relations. For example, in a delivery robot, a module that maintains balance may only have a few states. A module that must prioritize the delivery of multiple parcels to multiple people may have to reason about multiple individuals (e.g., people, packages, and rooms) and the relations between them. At a higher level, a module that reasons about the activity over the day may only require a few states to cover the different phases of the day (e.g., there might be three states of the robot: busy, available for requests, and recharging).
The planning horizon interacts with the modularity dimension. For example, at a high level, a dog may be getting an immediate reward when it comes and gets a treat. At the level of deciding where to place its paws, there may be a long time until it gets the reward, and so at this level it may have to plan for an indefinite stage.
Sensing uncertainty probably has the greatest impact on the complexity of reasoning. It is much easier for an agent to reason when it knows the state of the world than when it does not. Although sensing uncertainty with states is well understood, sensing uncertainty with individuals and relations is an active area of current research.
The uncertainty dimensions interact with the modularity dimension: at one level in a hierarchy, an action may be deterministic, whereas at another level, it may be stochastic. As an example, consider the result of flying to Paris with a companion you are trying to impress. At one level you may know where you are (in Paris); at a lower level, you may be quite lost and not know where you are on a map of the airport. At an even lower level responsible for maintaining balance, you may know where you are: you are standing on the ground. At the highest level, you may be very unsure whether you have impressed your companion.
Preference models interact with uncertainty because an agent needs to trade off between satisfying a major goal with some probability or a less desirable goal with a higher probability. This issue is explored in Section 9.1.
Multiple agents can also be used for modularity; one way to design a single agent is to build multiple interacting agents that share a common goal of making the higher-level agent act intelligently. Some researchers, such as Minsky , argue that intelligence is an emergent feature from a “society” of unintelligent agents.
Learning is often cast in terms of learning with features – determining which feature values best predict the value of another feature. However, learning can also be carried out with individuals and relations. Learning with hierarchies, sometimes called deep learning, has enabled the learning of more complex concepts. Much work has been done on learning in partially observable domains, and learning with multiple agents. Each of these is challenging in its own right without considering interactions with multiple dimensions.
The interaction dimension interacts with the planning horizon dimension in that when the agent is reasoning and acting online, it also needs to reason about the long-term horizon. The interaction dimension also interacts with the computational limits; even if an agent is reasoning offline, it cannot take hundreds of years to compute an answer. However, when it has to reason about what to do in, say 1/10 of a second, it needs to be concerned about the time taken to reason, and the trade-off between thinking and acting.
Two of these dimensions, modularity and bounded rationality, promise to make reasoning more efficient. Although they make the formalism more complicated, breaking the system into smaller components, and making the approximations needed to act in a timely fashion and within memory limitations, should help build more complex systems.