A Reduced Ordered Binary Decision Diagram (BDD) is a symbolic data structure introduced to the model checking community by Bryant in 1986 to help verify properties of systems with very large state spaces. Recently, BDDs have been used in heuristic search algorithms as an approach to representing and solving search problems with very large state spaces. However, these algorithms are still not memory efficient. This thesis presents a symbolic heuristic search algorithm that uses BDDs in a memory efficient way by performing bidirectional breadthirst heuristic search. The approach is evaluated empirically against existing symbolic methods and is shown to provide a significant improvement in performance.

No description available.

No description available.

This thesis represents a relatively new aspect of computing with regard to robotics. The need for fast, efficient collision avoidance algorithms is growing rapidly. Because conventional methods are complex and require vast amounts of computation, heuristic algorithms are more appealing. The focus of this thesis is the problem of moving a point through three dimensional space while avoiding known polyhedral obstacles. A heuristic algorithm to find shortest (near-optimal) collision-free paths in the presence of polyhedral obstacles, given initial and final positions, is presented. Previous methods for the problem rely on an a priori discretization of the space. The points in the discretization form nodes of a graph, and the collision avoidance problem is then solved by using some shortest path algorithm on the graph. The heuristic suggested here successively adds nodes to a graph, thus keeping the size of the graph manageable. The computational results are extremely encouraging.

The UK and the world are moving away from central energy resource to distributed generation (DG) in order to lower carbon emissions. Renewable energy resources comprise a big percentage of DGs and their optimal integration to the grid is the main attempt of planning/developing projects with in electricity network. Feasibility and thorough conceptual design studies are required in the planning/development process as most of the electricity networks are designed in a few decades ago, not considering the challenges imposed by DGs. As an example, the issue of voltage rise during steady state condition becomes problematic when large amount of dispersed generation is connected to a distribution network. The efficient transfer of power out or toward the network is not currently an efficient solution due to phase angle difference of each network supplied by DGs. Therefore optimisation algorithms have been developed over the last decade in order to do the planning purpose optimally to alleviate the unwanted effects of DGs. Robustness of proposed algorithms in the literature has been only partially addressed due to challenges of power system problems such multi-objective nature of them. In this work, the contribution provides a novel platform for optimum integration of distributed generations in power grid in terms of their site and size. The work provides a modified non-sorting genetic algorithm (NSGA) based on MATPOWER (for power flow calculation) in order to find a fast and reliable solution to optimum planning. The proposed multi-objective planning tool, presents a fast convergence method for the case studies, incorporating the economic and technical aspects of DG planning from the planner‟s perspective. The proposed method is novel in terms of power flow constraints handling and can be applied to other energy planning problems.

Master of Science / Department of Industrial & Manufacturing Systems Engineering / Todd Easton / Heuristics are often implemented to find better solutions to computationally challenging problems. Heuristics use varying techniques to search for quality solutions. Several optimization heuristics have drawn inspiration from real world practices. Ant colony optimization mimics ants in search of food. Genetic algorithms emulate traits being passed from a parent to a child. Simulated annealing imitates annealing metal. This thesis presents a new variable neighborhood search optimization heuristic, fútbol Strategies applied to Optimize Combinatorial problems to Create Efficient Results, which is called the SOCCER heuristic. This heuristic mimics fútbol and the closest player to the ball performs his neighborhood search and players are assigned different neighborhoods. The SOCCER heuristic is the first application of variable neighborhood search heuristic that uses a complex structure to select neighborhoods. The SOCCER heuristic can be applied to a variety of optimization problems. This research implemented the SOCCER heuristic for job shop scheduling problems. This implementation focused on creating a quality schedule for a local limestone company. A small computational study shows that the SOCCER heuristic can quickly solve complex job shop scheduling problems with most instances finishing in under an half an hour. The optimized schedules reduced the average production time by 7.27%. This is roughly a 2 day decrease in the number of days required to produce a month’s worth of orders. Thus, the SOCCER heuristic is a new optimization tool that can aid companies and researchers find better solutions to complex problems.

Approved for public release; distribution is unlimited / The U.S. Army Wartime Ammunition Distribution System (WADS) will experience an unprecedented demand for ammunition under the operational concept of Airland Battle. To meet demand, proper storage facility location and an efficient flow through the distribution network will be required. Using information from Army Field Manuals, maps and simulation data for demand, both a mixed integer program (MIP) and a sequential, optimization-based heuristic are developed to model the WADS. The Generalized Algebraic Modelling System is used to implement both models. The sequential heuristic locates ammunition facilities with a binary integer program and then directs ammunition through those facilities utilizing a network flow model with side constraints. The MIP integrates location and flow decisions in the same model. For a general scenario, the sequential heuristic locates a 21 node, 30 arc network with ammunition flows over 30 time periods in 22 CPU seconds on an IBM 3033AP. For the same scenario the MIP obtains a solution for only a 3 time period problem in 87 CPU seconds. Keywords: Ammunition, Integer programming, Heuristic, Networks / http://archive.org/details/gamsbasedmodelof00cain / Captain, United States Army

Master of Science - Science / Axial line placement is one step in a method known as space syntax which is used in town planning to analyse architectural structures. This is becoming increasingly important in the quickly growing urban world of today. The field of axial line placement is an area of space syntax that has previously been done manually which is becoming increasingly impractical. Research is underway to automate the process and this research forms a large part of the automation. The general problem of axial line placement has been shown to be NP-complete. For this reason, previous research in this field has been focused on finding special cases where this is not the case or finding heuristics that approximate a solution. The majority of the research conducted has been on the simpler case of axial line placement in configurations of orthogonal rectangles and the only work done with convex polygons has been in the restricted case of deformed urban grids. This document presents research that finds two non-trivial special cases of convex polygons that have polynomial solutions and finds the first heuristic for general configurations of convex polygons.

Thesis advisor: Jorge L.A. Garcia / When Odysseus sets sail from Circe’s island, she advises him to stop up his ears and eyes when he passes the Sirens or he will suffer terrible consequences. He makes his crew do it, but keeps his own senses clear, asking only to be tied to the mast so he cannot act on any bewitchments. This story could almost be an allegory about the moral danger of art. In this dissertation, I defend a small part of what I take to be the Odyssean thesis: that art is worth the danger it represents, and, specifically, that what I call "evil stories" are worth the danger they represent. The phrase "evil stories" is a shorthand, for me, for the longer phrase "stories which require us, in order to understand them, to imaginatively simulate the point of view of characters who commit acts of great harm for sadistic, malicious, or defiant reasons." I argue that auditing “evil stories” is not, for most people, and as part of a balanced imaginative diet, so morally dangerous that they ought to be avoided; moreover, I argue that it can be morally opportune to audit them and, in some special cases, morally obligatory. My strategy to defend this thesis is two part. First, I formulate and respond to what I take to be the most serious reasons to suspect that auditing evil stories is too morally dangerous. Those reasons include: the idea that auditing evil stories is itself an immoral action (chapter 3); the idea that it is a virtue to be unable to perform the mental operations involved in adequately auditing evil stories (chapter 4); the idea that understanding evil actions or characters is tantamount to condoning them (chapter 5); and the idea that being fascinated by evil undercuts one's standing to condemn it (chapter 6). Second, I venture several tentative arguments in support of the idea that evil stories can actually provide opportunities for moral growth and education: the idea that evil stories provoke unique and valuable kinds of moral reflection and that we can sometimes be obligated to audit them (chapter 7); and the idea that auditing evil stories is uniquely revelatory of some kind of moral truth (chapter 8). In the course of all this rebutting and reason giving, I propose a way of thinking about the ethics of audition in general which I call "role-centered response moralism," which develops obliquely across the subsections of various chapters. / Thesis (PhD) — Boston College, 2018. / Submitted to: Boston College. Graduate School of Arts and Sciences. / Discipline: Philosophy.

Providing robots with the ability to grasp objects has, despite decades of research, remained a challenging problem. The problem is approachable in constrained environments where there is ample prior knowledge of the scene and objects that will be manipulated. The challenge is in building systems that scale beyond specific situational instances and gracefully operate in novel conditions. In the past, heuristic and simple rule based strategies were used to accomplish tasks such as scene segmentation or reasoning about occlusion. These heuristic strategies work in constrained environments where a roboticist can make simplifying assumptions about everything from the geometries of the objects to be interacted with, level of clutter, camera position, lighting, and a myriad of other relevant variables. With these assumptions in place, it becomes tractable for a roboticist to hardcode desired behaviour and build a robotic system capable of completing repetitive tasks. These hardcoded behaviours will quickly fail if the assumptions about the environment are invalidated. In this thesis we will demonstrate how a robust grasping system can be built that is capable of operating under a more variable set of conditions without requiring significant engineering of behavior by a roboticist. This robustness is enabled by a new found ability to empower novel machine learning techniques with massive amounts of synthetic training data. The ability of simulators to create realistic sensory data enables the generation of massive corpora of labeled training data for various grasping related tasks. The use of simulation allows for the creation of a wide variety of environments and experiences exposing the robotic system to a large number of scenarios before ever operating in the real world. This thesis demonstrates that it is now possible to build systems that work in the real world trained using deep learning on synthetic data. The sheer volume of data that can be produced via simulation enables the use of powerful deep learning techniques whose performance scales with the amount of data available. This thesis will explore how deep learning and other techniques can be used to encode these massive datasets for efficient runtime use. The ability to train and test on synthetic data allows for quick iterative development of new perception, planning and grasp execution algorithms that work in a large number of environments. Creative applications of machine learning and massive synthetic datasets are allowing robotic systems to learn skills, and move beyond repetitive hardcoded tasks.