Browsing by Subject "Algorithms"

Now showing 1 - 13 of 13
  • Thumbnail Image
    Item
    Aggregating VMT within Predefined Geographic Zones by Cellular Assignment: A Non-GPS-Based Approach to Mileage- Based Road Use Charging
    (Intelligent Transportation Systems Institute, Center for Transportation Studies, University of Minnesota, 2012-08) Davis, Brian; Donath, Max
    Currently, most of the costs associated with operating and maintaining the roadway infrastructure are paid for by revenue collected from the motor fuel use tax. As fuel efficiency and the use of alternative fuel vehicles increases, alternatives to this funding method must be considered. One such alternative is to assess mileage based user fees (MBUF) based on the vehicle miles traveled (VMT) aggregated within the predetermined geographic areas, or travel zones, in which the VMT is generated. Most of the systems capable of this use Global Positioning Systems (GPS). However, GPS has issues with public perception, commonly associated with unwanted monitoring or tracking and is thus considered an invasion of privacy. The method proposed here utilizes cellular assignment, which is capable of determining a vehicle’s current travel zone, but is incapable of determining a vehicle’s precise location, thus better preserving user privacy. This is accomplished with a k-nearest neighbors (KNN) machine learning algorithm focused on the boundary of such travel zones. The work described here focuses on the design and evaluation of algorithms and methods that when combined, would enable such a system. The primary experiment performed evaluates the accuracy of the algorithm at sample boundaries in and around the commercial business district of Minneapolis, Minnesota. The results show that with the training data available, the algorithm can correctly detect when a vehicle crosses a boundary to within ±2 city blocks, or roughly ±200 meters, and is thus capable of assigning the VMT to the appropriate zone. The findings imply that a cellular-based VMT system may successfully aggregate VMT by predetermined geographic travel zones without infringing on the drivers’ privacy.
  • Thumbnail Image
    Item
    Algorithmically Recognizing Gait Variance from a Sensor-Based System
    (2019-05) Madden, Janna
    Detection of Vascular Dementia in early stages of Cognitive Impairment is difficult to do in a clinical setting since the earliest changes are often discrete and physiological in nature. One major aspect of this is gait patterns. This project utilizes force-sensing platforms, motion capture, and EMG sensors to unobtrusively collect biometric data from an individual’s walking gait patterns. Following data collection, a series of algorithms computes statistics off the gait cycles. In addition to previously validated biometric indicators of vascular dementia, including stride length, time in stride and swing phases of gait, time in dual leg vs single leg support, this system also examines metrics surrounding balance, lateral movement, and fine-grained gait analysis during critical transition periods of gait, when weight is transferred from one leg to the other. Secondly, by quantifying and analyzing machine learning algorithms, specifically deep learning time-series based models, onset patterns of vascular dementia are explored with an overarching goal of creating a system that will assist in understanding and diagnosing cases of vascular dementia. The proposed system provides a tool for which gait can be analyzed and compared over a long period of time and opens opportunity to increased personalization in health monitoring and disease diagnosis and provides an avenue to increase patient-centricity of medical care.
  • Thumbnail Image
    Item
    Arrow's Theorem and Turing Computability
    (Center for Economic Research, Department of Economics, University of Minnesota, 1994-08) Mihara, H. Reiju
    A social welfare function for an infinite society satisfies Pairwise Computability if for each pair (x, y) of alternatives, there exists an algorithm that can decide from a description of a profile on {x, y} whether the society prefers x to y. I prove that if a social welfare function satisfying Unanimity and Independence also satisfies Pairwise Computability, then it must be dictatorial. This result severely limits on practical grounds Fishburn's resolution (1970) of Arrow's impossibility. An interpretation of an infinite "society" is also given.
  • Thumbnail Image
    Item
    Automatic Generation of Traffic Signal Timing Plan
    (Minnesota Department of Transportation, 2014-09) Liu, Henry; Zheng, Jianfeng
    Due to budget constraints, most of the traffic signals in the US are retimed once every 2-5 years. Despite that, traffic delay increases 3-5% per year with outdated timing plans. It would be desirable to reduce the signal retiming costs by automating all or a portion of the manual process. This research takes one step forward in this direction. In this project, we develop a performance visualization and fine-tuning tool for arterial traffic signal systems, aimed at reducing the labor costs for signal retiming. Using high-resolution event-based data from the SMART-Signal system, a set of easy-to-use algorithms are developed to refine traffic signal systems. Specifically, a framework is developed to diagnose operational problems regarding cycle lengths, green splits and offsets. Then, algorithms for offsets and green splits fine-tuning are proposed. To fine-tune offsets, a practical procedure to construct time space diagram (TS-Diagram) to visualize the progression quality on arterials is proposed and validated. For green splits, an adjusted measure of effectiveness (MOE), the utilized green time (UGT), is proposed for performance evaluation. Moreover, a practical procedure for time of day (TOD) transitions is also developed to generate optimal timing plan schedules. Field case studies and simulation experiments are carried out to illustrate and validate the proposed algorithms. The algorithms could be used during the retiming process to help agencies reduce labor costs, or to periodically refine traffic signal systems for coordinated arterials.
  • Thumbnail Image
    Item
    CAD algorithms dealing with process and temperature effects in digital integrated circuits.
    (2010-01) Mogal, Hushrav
    The aggressive scaling trend of the semiconductor industry to improve integrated circuit performance manifests itself as process, voltage and temperature (PVT) variations which can negatively impact design yield. The aim of this work is to deal with process (P) and temperature (T) effects and to develop software CAD analysis and optimization tools to mitigate their effects on digital integrated circuit performance. In the first part of this thesis, we aim to develop an algorithm to compute the criticality of gates in a circuit with underlying process variations. The timing criticality of a gate indicates its impact on the overall timing performance of a circuit. We propose to use graph-based techniques to linearly traverse the timing graph of a digital circuit to obtain its criticality information. Such information can be useful to a designer or optimization tool in making decisions regarding gate sizing to improve the circuit performance. Our methodology must not only improve the speed of computation but also the accuracy with which we obtain the criticality values of gates in the circuit. In the second part of this thesis, we propose to deal with temperature effects in the presence of increased scaling of devices. The sub-threshold leakage power of a digital chip, which is the wasted power in a digital circuit without doing any useful work, is exponentially dependent on the operating temperature of the chip. We propose to use techniques to exploit this dependence to reduce the sub-threshold leakage power. By rearranging the physical placement we can affect the temperature distribution of various blocks on a digital chip, thereby also affecting the total sub-threshold leakage power. We aim to develop a physical floorplanning tool to alleviate the temperature and sub-threshold leakage power by taking into account their interdependence. This work proposes to use task migration (TM) as a methodology to deal with increasing sub-threshold leakage power in future technology nodes. The main idea is to replicate certain high-power blocks in the design, and migrate tasks at regular intervals from one part of the chip to another, thereby reducing the power density and temperature of the design. We aim to develop a CAD optimization framework using floorplanning to read in a circuit description and produce a physical floorplan layout of the TM-aware design. This involves the selection of the design blocks to replicate, followed by the judicious placement of the blocks and finally the selection of an appropriate migration interval taking into account its negative impact on circuit performance. The traditional semiconductor process technology consists of a single layer of silicon on which various devices like transistors and diodes are fabricated along with several layers of metal. Besides the problems outlined above, increasing device density is forcing larger die footprints. As a result, designers are facing increased congestion of routing wires, limiting the amount of performance benefit with scaling. Three-dimensional or vertical integration technology offers a promising alternative, in which multiple layers of silicon with their associated metal layers are stacked on top of each other. Field-programmable devices are particularly suited to such a technology due to the regular layout of logic and routing elements on the die. As the final part of this thesis, we examine the benefits of vertical integration applied to field programmable logic devices.
  • Thumbnail Image
    Item
    Environmental Monitoring with Unmanned Aerial Vehicles
    (2020-04) Stefas, Nikolaos
    Recent advances in miniaturization of processing units, storage capacity, battery power and sensory equipment have allowed Unmanned Aerial Vehicles (UAVs) to perform environmental monitoring tasks with unprecedented speed and accuracy. Data collection is important for algorithms and systems that try to learn how the physical world works or try to interact with it. The number, variety and quality of the data directly affects the performance of these algorithms. In order to fully realize this vision we need to compliment it with efficient systems that can collect the required data. In this dissertation we develop new robotic solutions for fully automating monitoring and data collection in natural, outdoor environments. First, we study the design of an Unmanned Aerial Vehicle (UAV) for safe tree surface inspection flying at low altitude inside orchard type fields. The objective of this study is threefold. The system needs to collect complete sets of data for different types of data collection sensors. Furthermore, it has to be able to operate successfully under the effects of wind disturbances. Finally, the integrity of the field has to be guaranteed. To achieve this goal, we modify and integrate several methods and technologies including a non-standard distance-velocity Proportional-Integral-Derivative (PID) based controller and real time obstacle map navigation based on occupancy voxels. The resulting system demonstrates successful operation and data collection inside a honeycrisp apple orchard. The demonstration includes multiple tests across several days, under various weather conditions (e.g. sunlight, wind) to ensure consistency and was shown to be fully functional even during GPS signal loss. Second, we study the problem of high altitude optimal trajectory generation for capturing aerial image footage of known but difficult to see areas (e.g. under trees or structures, reflective surfaces). In this problem we consider the relation between the camera resolution and UAV altitude. We associate each camera image with an inverted cone apexed at the location of the interest. The height of each cone is associated with the desired resolution and the apex angle corresponds to camera field of view. In other words, each cone encodes the set of view points from which a target can be imaged at a desired location. We provide a polynomial time approximation algorithm that produces a close to optimal solution and was evaluated in existing applications. We analyze the performance of our strategy and demonstrate through simulations and field experiments that by exploiting the special structure of the cones we can achieve shorter flight times than previously available solutions. The strategy can be used with any number of cones and split coverage into multiple flights in order to account for limited battery power or storage capacity. Third, we describe a method that can localize and approach a radio signal source at an unknown location with UAVs. We start by fitting a multi-rotor UAV system with a small on-board computer and a directional antenna that can detect the signal source. We then model the area around the signal source based on the antenna radiation field and classify the locations in which we can or cannot obtain reliable directionality measurements (i.e. bearing measurements). The results of this modeling resemble a cone-like region above the signal source inside of which bearing measurements are unreliable. In order to verify that our modeling is realistic, we also collect data with a real UAV system. Using this modeling, we develop a “home-in” strategy that takes advantage of a UAV’s ability to change altitude and exploits the special structure of the modeled conic-like region in order to approach the signal source from above. We analyze the performance of our strategy and demonstrate through simulations and field experiments that by exploiting this structure we can achieve short flight times. In this dissertation we make progress towards the creation of robotic sensing solutions that satisfy two important criteria. The first criterion is to provide theoretical guarantees about the performance of the proposed solutions. This is achieved by mathematically proving what the worst case scenario is and using it as an upper bound. The second criterion is to demonstrate the feasibility of the proposed solutions in real world applications. This is achieved by providing practical implementations tested in both simulations and with robotic systems operating in realistic settings.
  • Thumbnail Image
    Item
    Evaluation and Refinement of Minnesota Queue Warning Systems
    (Minnesota Department of Transportation, 2023-03) Hourdos, John; Robbennolt, Jake
    This study evaluates the first and a second implementations of the MN-QWARN queue warning algorithm developed by Hourdos et al. (1). This algorithm was developed to detect specific crash prone conditions created by traffic oscillations (shockwaves) on freeway systems. The MN-QWARN system was specifically calibrated for the freeway studied in Hourdos et al. (1) and was moved to a new location with minimal calibration. This evaluation found that the right-side model had a detection rate of 25% and a false alarm rate of 36%. The left-side model had a detection rate of 64% and a false alarm rate of 23%. We also note high over-warning rates on both lanes. Based on these findings, we recommend recalibrating the MN-QWARN algorithm at this location to examine improvements in performance.
  • Thumbnail Image
    Item
    Geometric search on point-tuples
    (2016-06) Agrawal, Akash
    Computational geometry is a branch of computer science that deals with the algorithmic aspects of geometric problems. Nearest neighbor search and range search are two fundamental geometric search problems in computational geometry. Despite the long history of these problems, the majority of the research until now has been focused on simple objects such as points. However, many applications such as trip planning under budget constraint, routing, task allocation, wireless sensor networks, etc. require querying more complex objects, such as point-tuples, that are created at the query time. Motivated by such considerations, this dissertation is devoted to the design of efficient algorithms and data structures for a relatively new class of geometric search problems where the goal is to report point-tuples that satisfy certain query constraints. Given several disjoint sets of points with an ordering of the sets, two fundamental search problems are addressed. The first problem is a point-tuple version of the nearest neighbor search problem, where the goal is to report the ordered sequence (i.e., tuple) of points (one per set and consistent with the given ordering of the sets) such that the total distance traveled starting from a query point q and visiting the points of the tuple in the specified order is minimum. The second problem is a point-tuple version of the range search problem, where, for a distance constraint δ, the goal is to report all the tuples of points (again, one per set and consistent with the given ordering of the sets) such that, for each tuple, the total distance traveled starting from q and visiting the points of the tuple is no more than δ. In many applications, the points also have feature attributes in addition to spatial attributes (coordinates). For such datasets, three extensions of the point-tuple version of the range search problem are also studied. These extensions differ in the type of constraint applied on the output tuples, as dictated by the underlying application. The first extension applies range constraints on the feature attribute values. The second extension applies a threshold constraint on the scores of the tuples, computed from the feature attribute values using an aggregation function (e.g., sum, product, etc.). Finally, the third extension seeks the so-called skyline of the output tuples based on the feature attribute values.
  • Thumbnail Image
    Item
    Improving intersection safety through variable speed limits for connected vehicles
    (Center for Transportation Studies, University of Minnesota, 2019-05) Levin, Michael; Chen, Rongsheng; Liao, Chen-Fu; Zhang, Tab
    Autonomous vehicles create new opportunities for innovative intelligent traffic systems. Variable speed limits, which is a speed management systems that can adjust the speed limit according to traffic condition or predefined speed control algorithm on different road segments, can be better implemented with the cooperation of autonomous vehicles. These compliant vehicles can automatically follow speed limits. However, non-compliant vehicles will attempt to pass the moving bottleneck created by the compliant vehicle. This project builds a multi-class cell transmission model to represent the relation between traffic flow parameters. This model can calculate flows of both compliant and non-compliant vehicles. An algorithm is proposed to calculate variable speed limits for each cell of the cell transmission model. This control algorithm is designed to reduce the stop-and-go behavior of vehicles at traffic signals. Simulation is used to test the effects of VSLs on an example network. The result shows that VSL is effective at reducing the energy consumption of the whole system and reduce the likelihood of crash occurrence.
  • Thumbnail Image
    Item
    Nurturing tagging communities
    (2009-03) Sen, Shilad Wieland
    Member contributions power many online communities. Users have uploaded billions of images to flickr, bookmarked millions pages on del.icio.us, and authored millions of encyclopedia articles at Wikipedia. Tags --- member contributed words or phrases that describe items --- have emerged as a powerful method for searching, organizing, and making sense of, these vast corpora. In this thesis we explore the dynamics, challenges, and possibilities of tagging systems. We study the way in which factors influencing an individual user's choice of tags can affect the evolution of community tags as a whole. Like other community-maintained systems, tagging systems can suffer from low quality contributions. We study interfaces and algorithms that can differentiate between low quality and high quality tags. Finally, we explore tagommenders, tag-based recommendation algorithms that combine the flexibility of tags with the automation of recommender systems. We base our explorations on tagging activity in the MovieLens movie recommendation system. We analyze tagging behavior, user studies, and surveys, of 97,000 tags and 3,600 users. Our results provide insight into the dynamics of existing tagging communities, and suggest mechanisms that address challenges of, and provide extensions to, tagging systems.
  • Thumbnail Image
    Item
    Placement and motion planning algorithms for robotic sensing systems
    (2014-10) Tokekar, Pratap Rajkumar
    Recent technological advances are making it possible to build teams of sensors and robots that can sense data from hard-to-reach places at unprecedented spatio-temporal scales. Robotic sensing systems hold the potential to revolutionize a diverse collection of applications such as agriculture, environmental monitoring, climate studies, security and surveillance in the near future. In order to make full use of this technology, it is crucial to complement it with efficient algorithms that plan for the sensing in these systems. In this dissertation, we develop new sensor planning algorithms and present prototype robotic sensing systems.In the first part of this dissertation, we study two problems on placing stationary sensors to cover an environment. Our objective is to place the fewest number of sensors required to ensure that every point in the environment is covered. In the first problem, we say a point is covered if it is seen by sensors from all orientations. The environment is represented as a polygon and the sensors are modeled as omnidirectional cameras. Our formulation, which builds on the well-known art gallery problem, is motivated by practical applications such as visual inspection and video-conferencing where seeing objects from all sides is crucial. In the second problem, we study how to deploy bearing sensors in order to localize a target in the environment. The sensors measure noisy bearings towards the target which can be combined to localize the target. The uncertainty in localization is a function of the placement of the sensors relative to the target. For both problems we present (i) lower bounds on the number of sensors required for an optimal algorithm, and (ii) algorithms to place at most a constant times the optimal number of sensors. In the second part of this dissertation, we study motion planning problems for mobile sensors. We start by investigating how to plan the motion of a team of aerial robots tasked with tracking targets that are moving on the ground. We then study various coverage problems that arise in two environmental monitoring applications: using robotic boats to monitor radio-tagged invasive fish in lakes, and using ground and aerial robots for data collection in precision agriculture. We formulate the coverage problems based on constraints observed in practice. We also present the design of prototype robotic systems for these applications. In the final problem, we investigate how to optimize the low-level motion of the robots to minimize their energy consumption and extend the system lifetime.This dissertation makes progress towards building robotic sensing systems along two directions. We present algorithms with strong theoretical performance guarantees, often by proving that our algorithms are optimal or that their costs are at most a constant factor away from the optimal values. We also demonstrate the feasibility and applicability of our results through system implementation and with results from simulations and extensive field experiments.
  • Thumbnail Image
    Item
    Resource management in wireless heterogeneous networks: an optimization perspective
    (2014-12) Sanjabi Boroujeni, Maziar
    In this dissertation we consider the central task of resource management in wireless Heterogeneous Networks (HetNets). Resource management plays an important role in satisfying the increasing need for wireless data in HetNets. Our emphasis is mainly on cross layer strategies. Various aspects of cross layer resource management can be formulated as optimization problems. Throughout this dissertation, we use advanced optimization techniques to develop algorithms that are capable of efficiently solving these optimization problems. First, we consider the joint base station assignment and linear {transceiver} design problem. In order to gain a better understanding of resource management problems, we analyze the complexity of solving the resulting optimization problem. We establish the NP-hardness of this problem for a wide range of system-wide utility functions.Due to the fundamental difficulty of globally solving these problems, our emphasis in the rest of this dissertation is on devising efficient algorithms that can approximately solve these problems under different practical limitations. One major practical limitation of current resource management strategies is the need for the channel state information at the transmitter side. In this thesis we consider transceiver design in wireless HetNet when the channel state information is incomplete/inexact. We propose a general stochastic successive upper-bound minimization approach to optimize the average/ergodic utility of the system. We specialize our method to obtain an efficient stochastic sum-rate maximization algorithm. The proposed algorithm can use the statistical knowledge instead of actual channel values and is guaranteed to converge to the set of stationary points of the stochastic sum-rate maximization problem. We further generalize our stochastic method to a cross layer framework for jointly optimizing the base station clustering and the downlink beamformers in a partial coordinated transmission scenario. The partial coordination is crucial in improving the overall system performance by reducing backhaul overhead. We validate the effectiveness of our methods via numerical experiments.
  • Thumbnail Image
    Item
    Statistical Methods for Optimally Locating Automatic Traffic Recorders
    (Mountain-Plains Consortium, 1992-07) Cheng, Chih-hsu; Nachtsheim, Christopher J.; Benson, P. George
    This report presents new computer-based statistical methods for the optimal placement of automatic traffic recorders (ATR). The goal of each method is to locate a set of ATRs so as to improve the overall efficiency and accuracy of Annual Average Daily Traffic (AADT) estimates. The precise estimation of AADTs is essential because of the important role they play in many highway design, maintenance, and safety decisions. Because of the huge number of potential ATR sites in a typical state highway, optimal selection of ATR sites is a very large combinatorial problem. Accordingly, site selection is currently accomplished through judgmental and/or design-based sampling techniques (e.g., random sampling). By developing fast and efficient computer algorithms to accomplish the purposive selection of an optimal sample, we demonstrate that model-based sampling is a viable alternative to classical design-based sampling techniques. The algorithms developed in this project include an exchange algorithm and a two-stage sampling algorithm. In the rank-1 exchange algorithm, ATR sites are sequentially added to and deleted from the design. It generates highly efficient designs without exhaustively searching through all possible designs. In the two-stage sampling approach, similar sites are statistically clustered, then approximate design techniques are used to calculate the optimal weight for each cluster. Based on these optimal weights, a random sample of sites is selected from within each cluster. The speed of this two-stage sampling algorithm makes it an ideal approach for large-scale problems. Using traffic data provided by the Minnesota Department of Transportation, we demonstrate empirically that both algorithms are substantially better in terms of average variance of prediction than simple random sampling.