| dc.description.abstract | Planning — developing strategies that an autonomous agent can use to achieve some desired goals — is a critical sub-part of the Artificial Intelligence literature. In general, planning problems involve single or multiple autonomous agents performing a series of actions that influence the agents’ environment to bring desired changes that help progress toward the agents’ goals. The computational challenge of identifying the progress-bringing actions depends upon the size of the planning problem of interest. This dissertation deviates from this traditional view of the agent-environment interaction and studies planning problems where components of the problem formulation exist that have minimal or no causal influence from the agent(s) actions. Such planning problems of this form have opportunities to realize computational efficiencies via decoupling.
At first glance, the premise of weak causation in actions might appear antithetical to the very idea of what plans (and actions) are for. After all, what will be the point of planning if actions do not cause changes in the environment? In fact, such situations often arise in existing problems and situations that model real-world scenarios, such as automated narrative generation, event narration, active perception, and situation depiction, to name a few. When causal influence is minor, traditional approaches that do not embrace this fact will treat the problem as a single component; this is a missed source of potential computational savings. Thus, approximate solutions are needed that consider each component separately. The approach taken here formulates the problem in a manner that essentially respects separate components, some under the agent’s influence while others are not. The research then utilizes the intrinsic properties of formulation to decouple the solution and, thereby, present efficient approximate solution techniques.
The research begins by tackling problems involving a single component of the environment uninfluenced by the agent’s action while having other elements that the agent has control over. We do this through example scenarios involving generation of structured narratives. First, we study the structured videography narrative capture problem where an autonomous videographer robot is tasked with observing its environment and later selectively summarizing what it saw as a vivid structured narrative. Second, we investigate the multi-agent version of the same, where a team of agents must coordinate to record events that fit some narrative structure. Next, we study problems involving multiple components that are not influenced by the agent’s action, and we do so in the guise of a scenario from the multi-commodity logistics problems. It involves an autonomous operations agent responsible for routing multiple commodities within a logistic network comprising multiple retail and storage units.
The three problem scenarios allow different opportunities for decoupling that this dissertation takes advantage of to provide efficient approximate solutions. For the structured videography narrative capture problem, the decoupling is in the form of separating the substance “what to capture?” from the style “how to capture?” allowing for an approximate solution. The multi-agent variation of the same decouples an agent’s decisions from the others. And lastly, the multi-commodity logistic scenario is solved by decoupling the analysis of parallel aspects of consumption.
For the problem scenarios mentioned above, the research conducts a thorough comparison of the various approaches to decoupling with the traditional solution. While the traditional approach — solving the problem jointly by searching over the state space and action space formed by the product of all the components — quickly becomes intractable, even with a few components. The approximate algorithms via decoupling are efficient and tractable and, in some specific cases, superior to the traditional approach. A multi-robot implementation of the structured videography narrative capture is also provided, showing the feasibility of the approximate solution approaches in the real world. | |
