Autonomous robots navigate unknown and known environments. Regions of the environment that are not suitable for navigation may be in the form of stationary obstacles, limitations of the robot, unfavourable terrain/structure of the environment and sudden appearance of unaccounted obstacles. In the context of robotics for known environments such as an automated industrial environment or a warehouse, the environment is known apriori. That is, locations of regions not favourable for path planning, called static constraints, are known. However, there is still a possibility of encountering obstacles that are not part of the known environment, called dynamic constraints. They could be human beings, other robots (either part of them or as a whole), components belonging to the environment (boxes, cables, tools, manufactured products) and anticipated dangers (spills, compromised structures). So, path planning in such an environment consists of the following general two steps. First, a path between the desired source and target representation is generated. Second, segments of the path are evaluated for any encounter with constraints. The two general steps are accomplished differently by different algorithms, each with merits and demerits. The differing success of approaches used, depends on how the environment is represented. In methods that aim to save memory, the map is generated by sampling; so, the map is only as good as the sampling method. Then, the produced path has to be periodically checked for whether a segment of the path is truly constraint-free (static and dynamic). Sometimes, the method may stagnate at a non-optimal path, or may even not be able to complete the process of finding one. Alternatively, in approaches that store a detailed grid based map, changes in terrain and structure are expensive memory costs. The problem thus remains open, with the aim of representing the map with only constraint-free, navigable regions and generating paths as a reaction to, or in anticipation of, encountering new constraints. To solve this open problem, the Constraint Free Discretized Manifold based Path Planner is proposed. The algorithm divides the problem into two parts: the first focuses on maximizing knowledge of the map using manifolds, and the second uses homology and homotopy classes to compute paths. The first step is instrumental in constructing a complete representation of the navigable space as a manifold, free of constraints known apriori. Using topological tools, this representation is shown to have favourable properties, such that any path generated on it is guaranteed to be constraint-free. So, on this constraint-free manifold, no segment of the path has to be explicitly evaluated for a collision with a known constraint. It is shown that alternative spaces associated with the environment also share the same properties under certain conditions. Thus, one can transform the constraint-free path to other equivalent spaces. The second step deals with new knowledge of constraints that render the originally produced path as invalid. Using homology and homotopy, paths on the original manifold can be recognized and avoided by tuning a parameter, thus resulting in an alternative constraint free path. By operating on the discretized constraint free manifold, path classes characterize uniqueness of paths around constraints. This designation provides the ability to avoid a specific path class, should that not be desirable in light of newly encountered constraints. Then, the algorithm can be queried for a new path class free of constraints, without any explicit modification of the original map created and even when there is no physical indication of constraints. Tuning may be performed to produce more than one alternative path to be on the manifold. The proposed algorithm is seen to produce paths on the manifold with an average percentage path length deviation of 29.6%, which is over 70% less than those produced by sampling algorithms. The proposed algorithm also provides an increase in retention of usable samples by a margin of at least 30%, when compared with sampling algorithms. This is while maintaining on-par run times at worst, and better run times in most cases, when evaluated against other algorithms. These general trends hold true even when the proposed algorithm is utilized to generate alternative paths. Any deviation in path length related trend is seen only when a query is made to generate an alternative path that avoids the shortest path previously generated; a feature not present in sampling algorithms.

This dissertation investigates how to plan paths for Unmanned Aerial Vehicles (UAV) for the task of covering an environment. Three increasingly complex coverage problems based on the environment that needs to be covered are studied. The dissertation starts with a 2D point coverage problem where the UAV needs to visit a set of sites on the ground plane by flying on a fixed altitude plane parallel to the ground. The UAV has limited battery capacity which may make it infeasible to visit all the points. A novel symbiotic UAV and Unmanned Ground Vehicle (UGV) system where the UGV acts as a mobile recharging station is proposed. A practical, efficient algorithm for solving this problem using Generalized Traveling Salesperson Problem (GTSP) solver is presented. Then the algorithm is extended to a coverage problem that covers 2D regions on the ground with a UAV that can operate in fixed-wing or multirotor mode. The algorithm is demonstrated through proof-of-concept experiments. Then this algorithm is applied to covering 2D regions, not all of which lie on the same plane. This is motivated by bridge inspection application, where the UAV is tasked with visually inspecting planar regions on the bridge. Finally, a general version of the problem where the UAV is allowed to fly in complete 3D space and the environment to be covered is in 3D as well is presented. An algorithm that clusters viewpoints on the surface of a 3D structure and has an UAV autonomously plan online paths to visit all viewpoints is presented. These online paths are re-planned in real time as the UAV obtains new information on the structure and strives to obtain an optimal 3D coverage path. / Doctor of Philosophy / This dissertation investigates how to plan paths for Unmanned Aerial Vehicles (UAV). Three increasingly complex coverage problems based on the environment that needs to be covered are studied. The dissertation starts with a 2D point coverage problem where the UAV needs to visit a set of sites on the ground by flying at a fixed altitude. The UAV has limited battery capacity which may make it impossible to visit all the points. A novel symbiotic UAV and Unmanned Ground Vehicle (UGV) system where the UGV acts as a mobile recharging station is proposed. A practical, efficient algorithm for solving this problem using Generalized Traveling Salesperson Problem (GTSP) solver is presented. Then the algorithm is extended to coverage of 2D regions on the ground with a hybrid UAV. The algorithm is demonstrated through proof-of-concept experiments. Then this algorithm is applied to covering 2D regions on 3D structures. This is motivated by bridge inspection application, where the UAV is tasked with visually inspecting regions on the bridge. Finally, a general version of the problem where the UAV is allowed to fly in 3D space and the environment to be covered is in 3D as well is presented. An algorithm that clusters points on the surface of a 3D structure and has an UAV autonomously plan online paths to visit all viewpoints is presented. These online paths are re-planned in real time as the UAV obtains new information on the structure and strives to obtain an optimal 3D coverage path.

This project is an addition to Cowgill Hall, the building that houses the College of Architecture on the Virginia Tech campus. Cowgill Hall is located on the north edge of campus, on a direct northern axis with the centerline of the campus drill field, which is the heart and center of the Va Tech Blacksburg campus. Cowgill Hall is a 4 story concrete and glass structure, built in 1969, with a dry moat-like hardscape on three sides around it and a wide bridge connecting the building at the second level to the campus via a large plaza. My solution was to use the bridge as the way to connect an addition to the existing Cowgill Hall building. By extending the bridge the axis is also extended, and the addition can become a terminus to the axis. I wanted the addition itself to promote and enhance the Va Tech School of Architecture methodology of design education, which is that of constructive exploration and student collaboration. Being able to observe the design process of other students seems to be fundamental to design education. Therefore, I sought to provide a design that would enhance the student's experience of a daily architectural education. The student experiences the building through a variety of pathways vertically through it, that path being a progression also of daylight to darkness, openness to closed, public to private. The path begins at the plaza, where the bridge takes the student from the campus into Cowgill Hall. My design extends the path out the other side of the building, creating another bridge. The addition is a semicircular four story form with a radial pattern of stair towers, with a slight skew and offset which serves to enhances a tension between the original Cowgill Hall building and the addition and thus become a dynamic large-occupancy gathering space and open lecture hall. The building structure is concrete and waffle slab. The exterior is two layers; the outer one comprised of stone and concrete, the inner one comprised of glass and steel. The building in plan is surrounded by ramps rising up and to the east, and the outer layer of the exterior supports a series of stacked and parallel ramps, which serves as one method of navigating the building vertically; one path. Always above the ramp is the inner layer, which consists of a slim-profile steel curtainwall glazing system. As the ramp moves towards ground level, the stone and concrete cladding peel away and the curtainwall expands, allowing more daylight and views in the desirable direction towards the mountains. The stone cladding is topped by precast concrete panels, the stone rising to the underside of the highest perimeter ramp on the building. which peels away as the building rises from the ground. The cladding consists of precast concrete and Virginia Bluestone, which is the stone most buildings on campus are built with. The bluestone is rough cut and heavy, and anchors the building to the site. Precast concrete tops the bluestone, aligning with the ramp, and easily allowing punched-openings to align squarely with the slope of the interior ramp system. The outer layer being heavy masonry grounds the building while giving it the mass and distinction that the surrounding Virginia Tech campus requires. The project's vertical structure is comprised of radial concrete walls which are in pairs. They support the waffle slab floor and roof structure, while housing the stairs. Movement inside the building vertically may be accomplished through any one of these radially located stair towers, which differ in their degree of solidity. Depending on the mood of the student or the educator, the path vertically can be chosen by the personal desire to be seen or to see others. One can sneak quietly or strut through the building openly. One can look through the stair walls to the student desks below and observe while being observed, or observe discreetly and without being intrusive. The path through the building is experiential, while the progression of spaces in the building provide unique and appropriate arenas for private introspection, collaboration and group learning. The spaces in tension create gathering spaces for education and reflection. The whole promote movement, observation and interaction. / Master of Architecture

Background: Just under half of pregnancies in the United States are unintended. And unintended births are particularly high among married and cohabiting adult women. Though family planning behaviors occur in a dyadic context with potentially joint influences of men and women on contraceptive use and pregnancy, most research on pregnancy and contraceptive use is based on reports from only women. Methods: I examined the pregnancy beliefs and contraceptive values of both members of cohabiting and married adult couples to determine how these individual-level characteristics come together at the dyad-level to shape pregnancy outcomes for the couple. I performed multinomial logit structural equation modeling analyses using longitudinal data from the National Couples Survey. I included demographic covariates that have been implicated in prior research as influential for contraceptive use and unintended pregnancy. Results: The male partner's pregnancy beliefs and contraceptive values significantly predicted dyadic risk of unintended pregnancy even after accounting for female partner's responses on these variables. Non-Hispanic Black race and low socioeconomic status emerged as risk factors. Discussion: This study indicates that dyadic analyses are needed to account for male partner influences to appropriately model risk for unintended pregnancy in research. The findings of this research also highlight demographic groups that may benefit from targeted dyadic intervention. / Ph. D.

This paper addresses sensitivity analysis questions concerning the shortest path problem and the maximum capacity path problem in an undirected network. For both problems, we determine the maximum and minimum weights that each edge can have so that a given path remains optimal. For both problems, we show how to determine these maximum and minimum values for all edges in O(m + K log K) time, where m is the number of edges in the network, and K is the number of edges on the given optimal path.

This study aims to look at the processes used when creating wellbeing economic projects to further understand what key themes there are. It applies Path-Dependency theory, consisting of Path-Dependence and Path-Creation to see if the chosen aspects are relevant to creating wellbeing projects and altering the path from the Anthropocene. Analysis is conducted on 45 implemented wellbeing economic projects from the Wellbeing Economy Alliance. After formulating questions based on this, interviews are carried out with ten experienced wellbeing leaders to gain a deeper understanding of what could be learned from their experiences of success and failure within wellbeing projects. The main findings of the study show that to effectively alter the path, power should be dispersed between as many people as possible, people are driven by a larger vision than specifics and it is essential for governments and the private sector to communicate with people to understand what they value in regards to wellbeing.

Most dynamic program analysis techniques such as profile-driven compiler optimizations, software testing and runtime property checking infer program properties by profiling one or more executions of a program. Unfortunately, program profiling does not come for free. For example, even the most efficient techniques for profiling acyclic, intra-procedural paths can slow down program execution by a factor of 2. In this thesis, we propose techniques that significantly lower the overheads of profiling paths, enabling the use of path-based dynamic analyzes in cost-sensitive environments. Preferential path profiling (PPP) is a novel software-only path profiling scheme that efficiently profiles given subsets of paths, which we refer to as interesting paths. The algorithm is based on the observation that most consumers of path profiles are only interested in profiling a small set of paths known a priori. Our algorithm can be viewed as a generalization of the Ball-Larus path profiling algorithm. Whereas the Ball-Larus algorithm assigns weights to the edges of a given CFG such that the sum of the weights of the edges along each path through the CFG is unique, our algorithm assigns weights to the edges such that the sum of the weights along the edges of interesting paths is unique. Furthermore, our algorithm attempts to achieve a minimal and compact encoding of the interesting paths; such an encoding significantly reduces the overheads of path profiling by eliminating expensive hash operations during profiling. Interestingly, we find that both the Ball-Larus algorithm and PPP are essentially a form of arithmetic coding. We use this connection to prove that the numbering produced by PPP is optimal. We also propose a programmable, non-intrusive hardware path profiler (HPP). The hardware profiler consists of a path detector that detects paths by monitoring the stream of retiring branch instructions emanating from the processor pipeline. The path detector can be programmed to detect various types of paths and track architectural events that occur along paths. The second component of the hardware profiling infrastructure is a Hot Path Table (HPT), that collects accurate hot path profiles. Our experimental evaluation shows that PPP reduces the overheads of profiling paths to 15% on average (with a maximum of 26%). The algorithm can be easily extended to profile inter-procedural paths at minimal additional overheads (average of 26%). We modeled HPP using a cycle-accurate superscalar processor simulator and find that HPP generates accurate path profiles at extremely low overheads (0.6% on average) with a moderate hardware budget. We also evaluated the use of PPP and HPP in a realistic profiling scenarios. We find that the profiles generated by HPP can effectively replace expensive profiles used in profile-driven optimizations. We also find that even well-tested programs tend to exercise a large number of untested paths in the field, emphasizing the need for efficient profiling schemes that can be deployed in production environments.

Obtaining an accurate whole program path (WPP) that captures a program’s runtime behaviour in terms of a control-flow trace has a number of well-known benefits, including opportunities for code optimization, bug detection, program analysis refinement, etc. Existing techniques to compute WPPs perform sub-optimal instrumentation resulting in significant space and time overheads. Our goal in this thesis is to minimize these overheads without losing precision. To do so, we design a novel and scalable whole program analysis to determine instrumentation points used to obtain WPPs. Our approach is divided into three components: (a) an efficient summarization technique for inter-procedural path reconstruction, (b) specialized data structures called conflict sets that serve to effectively distinguish between pairs of paths, and (c) an instrumentation algorithm that computes the minimum number of edges to describe a path based on these conflict sets. We show that the overall problem is a variant of the minimum hitting set problem, which is NP-hard, and employ various sound approximation strategies to yield a practical solution. We have implemented our approach and performed elaborate experimentation on Java programs from the DaCapo benchmark suite to demonstrate the efficacy of our approach across multiple dimensions. On average, our approach necessitates instrumenting only 9% of the total number of CFG edges in the program. The average runtime overhead incurred by our approach to collect WPPs is 1.97x, which is only 26% greater than the overhead induced by only instrumenting edges guaranteed to exist in an optimal solution. Furthermore, compared to the state-of-the-art, we observe a reduction in runtime overhead by an average and maximum factor of 2.8 and 5.4, respectively.

Orientador: Pedro Jose Catuogno / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatística e Computação Cientifica / Made available in DSpace on 2018-08-14T14:39:55Z (GMT). No. of bitstreams: 1 Castrequini_RafaelAndretto_M.pdf: 934326 bytes, checksum: e4c45bc1efde09bbe52710c44eab8bbf (MD5) Previous issue date: 2009 / Resumo: Introduzimos a teoria dos p-rough paths seguindo a abordagem de M. Gubinelli, conhecida por integração algébrica. Durante toda a dissertação nos restringimos ao caso 1 </= p < 3, o que e suficiente para lidar com trajetórias do movimento Browniano e aplicações ao Cálculo Estocástico. Em seguida, estudamos as equações diferenciais associadas aos rough paths, onde nós conectamos a abordagem de A. M. Davie (as equações) e a abordagem de M. Gubinelli (as integrais). No final da dissertação, aplicamos a teoria de rough path ao cálculo estocástico, mais precisamente relacionando as integrais de Itô e Stratonovich com a integral ao longo de caminhos. / Abstract: We introduce p-Rough Path Theory following M. Gubinelli_s approach, as known as algebraic integration. Throughout this masters thesis, we are concerned only in the case where 1 </= p < 3, witch is enough to deal with trajectories of a Brownnian motion and some applications to Stochastic Calculus. Afterwards, we study differential equations related to rough paths, where we connect the approach of A. M. Davie to equations with the approach of M. Gubinelli to integrals. At the end of this work, we apply the theory of rough paths to stochastic calculus, more precisely, we related the integrals of Itô and Stratonovich to integral along paths. / Mestrado / Sistemas estocasticos / Mestre em Matemática

We address the problem of all-pairs shortest time communication of messages in futuregeneration 6G networks by modeling the highly dynamic characteristics of the network using a temporal graph. Based on this model, an elegant technique is proposed to devise an algorithm for finding the all-pairs shortest time paths in the temporal graph that can be used for all-pairs internodes communication of messages in the network. The proposed algorithm basically involves computations similar to only two matrix multiplication steps, once in the forward direction and then in the backward direction.