Matching Items (6)
Filtering by

Clear all filters

151341-Thumbnail Image.png
Description
With the rapid development of mobile sensing technologies like GPS, RFID, sensors in smartphones, etc., capturing position data in the form of trajectories has become easy. Moving object trajectory analysis is a growing area of interest these days owing to its applications in various domains such as marketing, security, traffic

With the rapid development of mobile sensing technologies like GPS, RFID, sensors in smartphones, etc., capturing position data in the form of trajectories has become easy. Moving object trajectory analysis is a growing area of interest these days owing to its applications in various domains such as marketing, security, traffic monitoring and management, etc. To better understand movement behaviors from the raw mobility data, this doctoral work provides analytic models for analyzing trajectory data. As a first contribution, a model is developed to detect changes in trajectories with time. If the taxis moving in a city are viewed as sensors that provide real time information of the traffic in the city, a change in these trajectories with time can reveal that the road network has changed. To detect changes, trajectories are modeled with a Hidden Markov Model (HMM). A modified training algorithm, for parameter estimation in HMM, called m-BaumWelch, is used to develop likelihood estimates under assumed changes and used to detect changes in trajectory data with time. Data from vehicles are used to test the method for change detection. Secondly, sequential pattern mining is used to develop a model to detect changes in frequent patterns occurring in trajectory data. The aim is to answer two questions: Are the frequent patterns still frequent in the new data? If they are frequent, has the time interval distribution in the pattern changed? Two different approaches are considered for change detection, frequency-based approach and distribution-based approach. The methods are illustrated with vehicle trajectory data. Finally, a model is developed for clustering and outlier detection in semantic trajectories. A challenge with clustering semantic trajectories is that both numeric and categorical attributes are present. Another problem to be addressed while clustering is that trajectories can be of different lengths and also have missing values. A tree-based ensemble is used to address these problems. The approach is extended to outlier detection in semantic trajectories.
ContributorsKondaveeti, Anirudh (Author) / Runger, George C. (Thesis advisor) / Mirchandani, Pitu (Committee member) / Pan, Rong (Committee member) / Maciejewski, Ross (Committee member) / Arizona State University (Publisher)
Created2012
154901-Thumbnail Image.png
Description
Mobile Cloud computing has shown its capability to support mobile devices for

provisioning computing, storage and communication resources. A distributed mobile

cloud service system called "POEM" is presented to manage the mobile cloud resource

and compose mobile cloud applications. POEM considers resource management not

only between mobile devices and clouds, but also among mobile

Mobile Cloud computing has shown its capability to support mobile devices for

provisioning computing, storage and communication resources. A distributed mobile

cloud service system called "POEM" is presented to manage the mobile cloud resource

and compose mobile cloud applications. POEM considers resource management not

only between mobile devices and clouds, but also among mobile devices. It implements

both computation offloading and service composition features. The proposed POEM

solution is demonstrated by using OSGi and XMPP techniques.

Offloading is one major type of collaborations between mobile device and cloud

to achieve less execution time and less energy consumption. Offloading decisions for

mobile cloud collaboration involve many decision factors. One of important decision

factors is the network unavailability. This report presents an offloading decision model

that takes network unavailability into consideration. The application execution time

and energy consumption in both ideal network and network with some unavailability

are analyzed. Based on the presented theoretical model, an application partition

algorithm and a decision module are presented to produce an offloading decision that

is resistant to network unavailability.

Existing offloading models mainly focus on the one-to-one offloading relation. To

address the multi-factor and multi-site offloading mobile cloud application scenarios,

a multi-factor multi-site risk-based offloading model is presented, which abstracts the

offloading impact factors as for offloading benefit and offloading risk. The offloading

decision is made based on a comprehensive offloading risk evaluation. This presented

model is generic and expendable. Four offloading impact factors are presented to show

the construction and operation of the presented offloading model, which can be easily

extended to incorporate more factors to make offloading decision more comprehensive.

The overall offloading benefits and risks are aggregated based on the mobile cloud

users' preference.

The offloading topology may change during the whole application life. A set of

algorithms are presented to address the service topology reconfiguration problem in

several mobile cloud representative application scenarios, i.e., they are modeled as

finite horizon scenarios, infinite horizon scenarios, and large state space scenarios to

represent ad hoc, long-term, and large-scale mobile cloud service composition scenarios,

respectively.
ContributorsWu, Huijun (Author) / Huang, Dijiang (Thesis advisor) / Xue, Guoliang (Committee member) / Dasgupta, Partha (Committee member) / Mirchandani, Pitu (Committee member) / Arizona State University (Publisher)
Created2016
154558-Thumbnail Image.png
Description
Feature learning and the discovery of nonlinear variation patterns in high-dimensional data is an important task in many problem domains, such as imaging, streaming data from sensors, and manufacturing. This dissertation presents several methods for learning and visualizing nonlinear variation in high-dimensional data. First, an automated method for discovering nonlinear

Feature learning and the discovery of nonlinear variation patterns in high-dimensional data is an important task in many problem domains, such as imaging, streaming data from sensors, and manufacturing. This dissertation presents several methods for learning and visualizing nonlinear variation in high-dimensional data. First, an automated method for discovering nonlinear variation patterns using deep learning autoencoders is proposed. The approach provides a functional mapping from a low-dimensional representation to the original spatially-dense data that is both interpretable and efficient with respect to preserving information. Experimental results indicate that deep learning autoencoders outperform manifold learning and principal component analysis in reproducing the original data from the learned variation sources.

A key issue in using autoencoders for nonlinear variation pattern discovery is to encourage the learning of solutions where each feature represents a unique variation source, which we define as distinct features. This problem of learning distinct features is also referred to as disentangling factors of variation in the representation learning literature. The remainder of this dissertation highlights and provides solutions for this important problem.

An alternating autoencoder training method is presented and a new measure motivated by orthogonal loadings in linear models is proposed to quantify feature distinctness in the nonlinear models. Simulated point cloud data and handwritten digit images illustrate that standard training methods for autoencoders consistently mix the true variation sources in the learned low-dimensional representation, whereas the alternating method produces solutions with more distinct patterns.

Finally, a new regularization method for learning distinct nonlinear features using autoencoders is proposed. Motivated in-part by the properties of linear solutions, a series of learning constraints are implemented via regularization penalties during stochastic gradient descent training. These include the orthogonality of tangent vectors to the manifold, the correlation between learned features, and the distributions of the learned features. This regularized learning approach yields low-dimensional representations which can be better interpreted and used to identify the true sources of variation impacting a high-dimensional feature space. Experimental results demonstrate the effectiveness of this method for nonlinear variation pattern discovery on both simulated and real data sets.
ContributorsHoward, Phillip (Author) / Runger, George C. (Thesis advisor) / Montgomery, Douglas C. (Committee member) / Mirchandani, Pitu (Committee member) / Apley, Daniel (Committee member) / Arizona State University (Publisher)
Created2016
158577-Thumbnail Image.png
Description
This dissertation focuses on three large-scale optimization problems and devising algorithms to solve them. In addition to the societal impact of each problem’s solution, this dissertation contributes to the optimization literature a set of decomposition algorithms for problems whose optimal solution is sparse. These algorithms exploit problem-specific properties and use

This dissertation focuses on three large-scale optimization problems and devising algorithms to solve them. In addition to the societal impact of each problem’s solution, this dissertation contributes to the optimization literature a set of decomposition algorithms for problems whose optimal solution is sparse. These algorithms exploit problem-specific properties and use tailored strategies based on iterative refinement (outer-approximations). The proposed algorithms are not rooted in duality theory, providing an alternative to existing methods based on linear programming relaxations. However, it is possible to embed existing decomposition methods into the proposed framework. These general decomposition principles extend to other combinatorial optimization problems.

The first problem is a route assignment and scheduling problem in which a set of vehicles need to traverse a directed network while maintaining a minimum inter-vehicle distance at any time. This problem is inspired by applications in hazmat logistics and the coordination of autonomous agents. The proposed approach includes realistic features such as continuous-time vehicle scheduling, heterogeneous speeds, minimum and maximum waiting times at any node, among others.

The second problem is a fixed-charge network design, which aims to find a minimum-cost plan to transport a target amount of a commodity between known origins and destinations. In addition to the typical flow decisions, the model chooses the capacity of each arc and selects sources and sinks. The proposed algorithms admit any nondecreasing piecewise linear cost structure. This model is applied to the Carbon Capture and Storage (CCS) problem, which is to design a minimum-cost pipeline network to transport CO2 between industrial sources and geologic reservoirs for long-term storage.

The third problem extends the proposed decomposition framework to a special case of joint chance constraint programming with independent random variables. This model is applied to the probabilistic transportation problem, where demands are assumed stochastic and independent. Using an empirical probability distribution, this problem is formulated as an integer program with the goal of finding a minimum-cost distribution plan that satisfies all the demands with a minimum given probability. The proposed scalable algorithm is based on a concave envelop approximation of the empirical probability function, which is iteratively refined as needed.
ContributorsMatin Moghaddam, Navid (Author) / Sefair, Jorge (Thesis advisor) / Mirchandani, Pitu (Committee member) / Escobedo, Adolfo (Committee member) / Grubesic, Anthony (Committee member) / Arizona State University (Publisher)
Created2020
171460-Thumbnail Image.png
Description
Arc Routing Problems (ARPs) are a type of routing problem that finds routes of minimum total cost covering the edges or arcs in a graph representing street or road networks. They find application in many essential services such as residential waste collection, winter gritting, and others. Being NP-hard, solutions are

Arc Routing Problems (ARPs) are a type of routing problem that finds routes of minimum total cost covering the edges or arcs in a graph representing street or road networks. They find application in many essential services such as residential waste collection, winter gritting, and others. Being NP-hard, solutions are usually found using heuristic methods. This dissertation contributes to heuristics for ARP, with a focus on the Capacitated Arc Routing Problem (CARP) with additional constraints. In operations such as residential waste collection, vehicle breakdown disruptions occur frequently. A new variant Capacitated Arc Re-routing Problem for Vehicle Break-down (CARP-VB) is introduced to address the need to re-route using only remaining vehicles to avoid missing services. A new heuristic Probe is developed to solve CARP-VB. Experiments on benchmark instances show that Probe is better in reducing the makespan and hence effective in reducing delays and avoiding missing services. In addition to total cost, operators are also interested in solutions that are attractive, that is, routes that are contiguous, compact, and non-overlapping to manage the work. Operators may not adopt a solution that is not attractive even if it is optimum. They are also interested in solutions that are balanced in workload to meet equity requirements. A new multi-objective memetic algorithm, MA-ABC is developed, that optimizes three objectives: Attractiveness, makespan, and total cost. On testing with benchmark instances, MA-ABC was found to be effective in providing attractive and balanced route solutions without affecting the total cost. Changes in the problem specification such as demand and topology occurs frequently in business operations. Machine learning be applied to learn the distribution behind these changes and generate solutions quickly at time of inference. Splice is a machine learning framework for CARP that generates closer to optimum solutions quickly using a graph neural network and deep Q-learning. Splice can solve several variants of node and arc routing problems using the same architecture without any modification. Splice was trained and tested using randomly generated instances. Splice generated solutions faster that are also better in comparison to popular metaheuristics.
ContributorsRamamoorthy, Muhilan (Author) / Syrotiuk, Violet R. (Thesis advisor) / Forrest, Stephanie (Committee member) / Mirchandani, Pitu (Committee member) / Sen, Arunabha (Committee member) / Arizona State University (Publisher)
Created2022
187307-Thumbnail Image.png
Description
Networks are a versatile modeling tool for the cyber and physical infrastructure that characterize society. They can be used to describe system spatiotemporal dynamics, including distribution of commodities, movement of agents, and data transmission. This flexibility has resulted in the widespread use of network optimization techniques for decision-making in telecommunications,

Networks are a versatile modeling tool for the cyber and physical infrastructure that characterize society. They can be used to describe system spatiotemporal dynamics, including distribution of commodities, movement of agents, and data transmission. This flexibility has resulted in the widespread use of network optimization techniques for decision-making in telecommunications, transportation, commerce, among other systems. However, realistic network problems are typically large-scale and require the use of integer variables to incorporate design or logical system constraints. This makes such problems hard to solve and precludes their wide applicability in the solution of applied problems. This dissertation studies four large-scale optimization problems with underlying network structure in different domain applications, including wireless sensor networks, wastewater monitoring, and scheduling. The problems of interest are formulated using mixed-integer optimization formulations. The proposed solution approaches in this dissertation include branch-and-cut and heuristic algorithms, which are enhanced with network-based valid inequalities and network reduction techniques. The first chapter studies a relay node placement problem in wireless sensor networks, with and without the presence of transmission obstacles in the deployment region. The proposed integer linear programming approach leverages the underlying network structure to produce valid inequalities and network reduction heuristics, which are incorporated in the branch-and-bound exploration. The solution approach outperforms the equivalent nonlinear model and solves instances with up to 1000 sensors within reasonable time. The second chapter studies the continuous version of the maximum capacity (widest) path interdiction problem and introduces the first known polynomial time algorithm to solve the problem using a combination of binary search and the discrete version of the Newton’s method. The third chapter explores the service agent transport interdiction problem in autonomous vehicle systems, where an agent schedules service tasks in the presence of an adversary. This chapter proposes a single stage branch-and-cut algorithm to solve the problem, along with several enhancement techniques to improve scalability. The last chapter studies the optimal placement of sensors in a wastewater network to minimize the maximum coverage (load) of placed sensors. This chapter proposes a branch-and-cut algorithm enhanced with network reduction techniques and strengthening constraints.
ContributorsMitra, Ankan (Author) / Sefair, Jorge A (Thesis advisor) / Mirchandani, Pitu (Committee member) / Grubesic, Anthony (Committee member) / Byeon, Geunyeong (Committee member) / Arizona State University (Publisher)
Created2023