Browsing by Subject "Spatio-temporal"

Now showing 1 - 3 of 3
  • Thumbnail Image
    Item
    Representation and reasoning for complex spatio-temporal problems: from humans to software agents
    (2014-03) Wetzel, Christopher Baylor
    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.
  • Thumbnail Image
    Item
    ST-Hadoop: A MapReduce Framework for Big Spatio-temporal Data Management
    (2019-05) Alarabi, Louai
    Apache Hadoop, employing the MapReduce programming paradigm, that has been widely accepted as the standard framework for analyzing big data in distributed environments. Unfortunately, this rich framework was not genuinely exploited towards processing large scale spatio-temporal data, especially with the emergence and popularity of applications that create them in large-scale. The huge volumes of spatio-temporal data come from applications, like Taxi fleet in urban computing, Asteroids in astronomy research studies, animal movements in habitat studies, neuron analysis in neuroscience research studies, and contents of social networks (e.g., Twitter or Facebook). Managing space and time are two fundamental characteristics that raised the demand for processing spatio-temporal data created by these applications. Besides the massive size of data, the complexity of shapes and formats associated with these data raised many challenges in managing spatio-temporal data. The goal of the dissertation is centered on establishing a full-fledged big spatio-temporal data management system that serves the need for a wide range of spatio-temporal applications. This involves indexing, querying, and analyzing spatio-temporal data. We propose ST-Hadoop; the first full-fledged open-source system with native support for big spatio-temporal data, available to download http://st-hadoop.cs.umn.edu/. ST- Hadoop injects spatio-temporal data awareness inside the highly popular Hadoop system that is considered state-of-the-art for off-line analysis of big data systems. Considering a distributed environment, we focus on the following: (1) indexing spatio-temporal data and (2) Supporting various fundamental spatio-temporal operations, such as range, kNN, and join (3) Supporting indexing and querying trajectories, which is considered as a special class of spatio-temporal data that require special handling. Throughout this dissertation, we will touch base on the background and related work, motivate for the proposed system, and highlight our contributions.
  • Thumbnail Image
    Item