Representation and Reasoning for Complex Spatio-Temporal Problems: From Humans to Software Agents

Success in the real world depends on the ability to reason about space and time. Consider the simple, everyday task of deciding whether to cross a road. If a car is coming, your decision will be based on how wide the road is, how fast you walk, how far away the car is and how fast it is moving. You might also consider structural features of the road; if the car has to turn a corner or go over a speed bump, the car will move slower for a short period of time. Determining whether it is safe to cross requires reasoning about the interaction of these variables.;The field of artificial intelligence has developed representations for describing space (e.g., RCC) and time (e.g., interval calculus) but not for describing the interaction between the two. Unsurprisingly, billions of years of evolution have resulted in humans being quite good at it. How they do so is not completely understood. Detailed studies have focused on overly simple problems while studies of complex problems have lacked sufficient detail to build computer models.;This thesis describes our investigation into solving problems with significant spatio-temporal components. We focused on the domain of tower defense puzzles, a class of complex spatio-temporal problems that requires the problem solver to use spatial actions (placing guard towers on a map) to maximize a temporal variable (tower active time). We had two objectives. First, using methods from experimental psychology and computational behavioral modeling, we wished to understand how, precisely, humans solved these problems. Humans, unlike computers, are known to be good at solving this type of problem. Our second goal was to construct a computer agent capable of solving this task as well as or better than the best humans.;To investigate the relationship of space, time and problem solving, we performed two experiments. The goal of Experiment 1 was to determine how humans solved tower defense puzzles. Experienced tower defense solvers (n=38) were asked to solve a series of novel tower defense puzzles. Interviews and automated data capture tools provided data that were used to answer a set of questions on how humans solved these puzzles. The results showed a tight integration between problem, representation and reasoning. Subjects needed to manipulate space to maximize a temporal value. Rather than represent the space, they represented the goal-relevant opportunities for actions present in the space, known as affordances. Problems were decomposed into sets of goals, each goal was addressed by one or more simple, focused, goal-specific strategies and each strategy was activated by an affordance. An interesting finding was that many subjects treated temporal problems as if they were spatial ones, which we refer to as spatial proxying.;The goal of Experiment 2 was to determine how well the discovered strategies worked. Novice (n=10) and experienced (n=10) tower defense solvers were asked to solve a series of novel tower defense puzzles. Results showed that 70% of novice and 40% of experienced subjects used spatial proxying strategies and that these strategies worked surprisingly well. 10% of novice and 60% of experienced subjects used strategies that directly manipulated time. These strategies performed better but frequently created solutions that were counter-intuitive.;Our second objective was to investigate computational representations and algorithms capable of creating an agent that performs at or above human levels for this task. Human studies showed that the majority of the "intelligence" of their problem solving process lay in the recognition and representation of spatial affordances. This led to the creation of the Spatial Affordance Query System (SAQS). In this system, spatio-temporal reasoning agents are created declaratively, with the author specifying the strategies the agent knows. The agent and problem map are passed to a solver, which compares the agent's strategy set to the affordances reported by SAQS, which instantiates the applicable strategies. The majority of agents were 5-12 lines of code and the best agent performed at the same level as the best human subjects.