Deductive Approach to Processing High-Level Activity Queries in UAV Networks
Explore a deductive approach for processing high-level activity queries in UAV networks, focusing on representing and optimizing queries in an energy-efficient manner for distributed evaluation. The model involves UAVs detecting local activities through sensors, with queries translated into distributed code for optimization. Logic programming and declarative frameworks are utilized for expressing collaborative functionality and automating optimizations within the network.
Uploaded on | 1 Views
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Deductive Approach to Processing High-Level Activity Queries in UAV Networks Himanshu Gupta Stony Brook University
Abstract Envision a network of UAVs deployed to recognize high-level (video) activities. E.g., two vehicles driving away from an explosion in different directions. How to represent such queries? We propose a deductive approach. Why? Declarative, and facilitates energy-efficient evaluation. Key challenge: Develop techniques for efficient distributed evaluation. We present some preliminary ideas. 2
Outline UAV network model Representation of high-level activity queries Introduction to deductive programming Query Evaluation and Optimization Ideas Future Plan 3
UAV Network Model A network of UAVs (e.g., drones, blimps). Each UAV capable of detecting local low- level (short) activities (e.g., object recognition) via video sensors and image processing. Each activity query translated into optimized distributed code over the drones. Motivating Scenario: Ad hoc deployment for event or battlefield monitoring. 4
Representation of Activity Queries A declarative (what, not how) framework needed to facilitate automated optimization and distributed evaluation. Deductive/Logic Approach. Motivation: UAVs gather low-level facts (can be represented as tuples in a table). Collaborative functionality is easy to express using logic rules; rest is embedded in built-in functions. Amenable to optimization. Turing complete (with function symbols, and recursion) 5
Background: Logic Programming Manipulation of facts (tuples of a table). E.g., Vehicle(x,y,t) may represent detection of vehicle at location (x,y) and time t. Program = a set of logic rules. Logic rule: H G1, G2, . Gk where each is of the form predicate (arguments). 6
Example Query: Two persons approach from different directions, get into a standing car, and drive away. Representation (sketch): <activity> Trajectory(direction), Trajectory(direction2), StaticObject(S), converge(direction, direction2, S) 7
Expressibility Datalog is the simplest deductive language. Includes recursion and negation. Adding lists or function symbols makes it Turing Complete. 8
Overall Framework Base data streams generated over the distributed network Logic programs over these streams Compile programs to distributed code Need efficient query evaluation techniques 9
Query Costs Computation cost: Join of tables, image processing, rule evaluation. Communication cost: Communication of images, facts between UAVs. Energy Cost: Movement of the UAVs, e.g., to cover certain areas, to detect desired objects. Key cost objective is to minimize energy cost, which is dominated by movement of the UAVs and perhaps, image processing. Minimize synthesis of low-level facts. 10
Query Optimization Traditional approaches have minimized join costs. Here, we (only) minimize synthesize of low- level facts. Opens up new challenges, esp. in the context of streaming spatio-temporal data. 11
Query Evaluation: Nave approaches Synthesize all possible facts. Very inefficient. Pure top down: Not useful, if there is no binding or only real-time binding (too late to synthesize a desired fact). Negation may cause problems. Pure bottom-up: Requires all low-level facts; too inefficient. Optimizations (semi-naive, magic sets) are tailored to minimize join cost. 12
Query Optimization Ideas: I Key Optimization: Order and prune synthesis. Example: Query: Two persons approach from different directions to a stationary car, and then drive away . Recognizing a stationary car may be much cheaper, and thus, should be done before any persons are tracked . 13
Query Optimization Ideas: II Data Acquisition Cost (Movement of UAVs): Can be optimized by synthesizing subgoals in the order of temporal precedence. Incorporate Stationary subgoals (e.g., stationary car), or subgoals with spatial binding. Data Processing Cost (Image processing): Minimization would require an optimization scheme (greedy?) based on appropriate cost model. Communication Cost can be largely eliminated by communicating only facts, and not images. 14
Future Plan Develop a comprehensive query evaluation scheme based on the given ideas. Such a scheme would indirectly minimize overall movement of the UAVs, while recognizing the defined activities. 15
