The JHU/APL Path Planning team has developed path planning techniques to look for paths that balance the utility and risk associated with different routes through a minefield. Extending on previous years' efforts, we investigated real-world Naval mine avoidance requirements and developed a tactical decision aid (TDA) that satisfies those requirements. APL has developed new mine path planning techniques using graph based and genetic algorithms which quickly produce near-minimum risk paths for complicated fitness functions incorporating risk, path length, ship kinematics, and naval doctrine. The TDA user interface, a Java Swing application that obtains data via Corba interfaces to path planning databases, allows the operator to explore a fusion of historic and in situ mine field data, control the path planner, and display the planning results. To provide a context for the minefield data, the user interface also renders data from the Digital Nautical Chart database, a database created by the National Geospatial-Intelligence Agency containing charts of the world's ports and coastal regions. This TDA has been developed in conjunction with the COMID (Cooperative Organic Mine Defense) system. This paper presents a description of the algorithms, architecture, and application produced.
We have been developing path planning techniques to look for paths
that balance the utility and risk associated with different routes through a minefield. Such methods will allow a battlegroup commander to evaluate alternative route options while searching for low risk paths. Extending on previous years' efforts, we have implemented a generalized path planning framework to allow rapid evaluation and integration of new path planning algorithms. We have also implemented
a version of Rapidly-Explored Random Trees (RRTs) for mine path planning which integrates path risk, path time, and dynamic and kinematic concerns. Several variants of the RRT algorithm and our existing path planning algorithms were quantitatively evaluated using the generalized path planning framework and an algorithm-dynamic evaluation graphical user interface.
We have developed path-planning techniques and tools to look for paths through minefields. Our techniques seek to balance the length and risk associated with different routes through a minefield. Our methods are intended to provide battlegroup commanders powerful new tools to evaluate alternative routes while searching for low risk paths. It is well known how to find the path of shortest distance, and well known how to find the path of least risk. However, to optimize both criteria at once is a challenging problem. We have developed and compared two methods for multi-criteria path planning. We have found that the better method uses a linear combination of the criteria with a user selected risk tolerance parameter. We describe algorithms for finding the fasted bounded-risk path. We also describe the novel use of dynamic graph algorithms to quickly find new paths as the risk is changed due to the neutralization (deletion) of mines and the discovery (insertion) of mines. We will also describe an algorithm used to convert paths to a set of straight-line paths for ship navigation. Our tool allows a commander to find a path of acceptable length and risk, to explore the effect of eliminating mines, and to obtain a set of waypoints for minefield navigation.
We have been developing path planning techniques to look for paths that balance the utility and risk associated with different routes through a minefield. Such methods will allow a battlegroup commander to evaluate alternative route options while searching for low risk paths. A risk management framework can be used to describe the relative values of different factors such as risk versus time to objective, giving the commander the capability to balance path safety against other mission objectives. We will describe our recent investigations of two related path planning problems in this framework. We have developed a stochastic search technique to identify low risk paths that satisfy a constraint on the transit time. The objective is to generate low risk paths quickly so that the user can interactively explore the time-risk tradeoff. We will compare this with the related problem of finding the fastest bounded-risk path, and the potential use of dynamic graph algorithms to quickly find new paths as the risk bound is varied.
The future success of Navy-Marine Corps operations in the extended littoral battlespace will depend critically on organic mine countermeasure capabilities. A battlegroup commander will require tools to rapidly detect, classify, and identify mines and form a tactical picture of mined areas, so a decision can be made to punch through the minefield, avoid it, or wait for dedicated mine countermeasures forces to clear it. We introduce here a command and control framework for mine countermeasures based on probabilistic classification and multicriteria path planning under uncertainty. Data from probabilistic mine classifiers can be used by a path planning tool to generate information comparing the relative utility and risk associated with different routes through a minefield. We are developing a dynamic path planning tool that can be adjusted to manage safety versus time to objective, constructing alternate paths of varying time and risk through a minefield. It will evaluate alternative routes while searching for low risk paths. A risk management framework can be used to describe the relative values of such different factors as risk versus time to objective, giving the capability to balance path safety against other mission objectives. We are also adding visualization techniques to display mines with uncertain locations and highlight alternative routes through minefields and obstacles. Our goal is to present a commander the most useful tactical picture of mined areas for decision-making.
An important goal in interactive computer graphics is to allow the user to interact dynamically with three-dimensional objects. The computing resources required to represent, transmit and display a three dimensional object depends on the number of polygons used to represent it. Many geometric simplification algorithms have been developed to represent the geometry with as few polygons as possible, without substantially changing the appearance of the rendered object. A popular method for achieving geometric simplification is to replace fine scale geometric detail with texture images mapped onto the simplified geometry. However the effectiveness of replacing geometry with texture has not been explored experimentally. In this paper we describe a visual experiment in which we examine the perceived quality of various representations of textured, geometric objects, viewed under direct and oblique illumination. We used a pair of simple large scale objects with different fine-scale geometric detail. For each object we generated many representations, varying the resources allocated to geometry and texture. The experimental results show that while replacing geometry with texture can be very effective, in some cases the addition of texture does not improve perceived quality, and can sometimes reduce the perceived quality.
Computing discrete 2D convolutions is an important problem in image processing. In mathematical morphology, an important variant is that of computing binary convolutions, where large kernels are involved. In this paper, we present an algorithm for computing convolutions of this form, where the kernel of the binary convolution is derived from a convex polygon. Because the kernel is a geometric object, we allow the algorithm some flexibility in how it elects to digitize the convex kernel at each placement, as long as the digitization satisfies certain reasonable requirements. We say that such a convolution is valid. Given this flexibility we show that it is possible to computer binary convolutions more efficiently than would normally be possible for large kernels, computes a valid convolution in time O(kmn) time. Unlike standard algorithms for computing correlations and convolutions, the running time is independent of the area or perimeter of K, and our technique do not rely on computing fast Fourier transforms. Our algorithm is based on a novel use of Bresenham's line-drawing algorithm and prefix-sums to update the convolution efficiently as the kernel is moved from one position to another across the image.
We consider the problem of identifying one of a set of polygonal models in the plane using point probes and finger probes. In particular, we give strategies for using a minimum number of finger probes to determine a finite number of possible locations of an unknown interior point p in one of the models. A finger probe takes as input an interior point p of a polygon P and a direction (Theta) , and it outputs the first point of intersection of a ray emanating from p in direction (Theta) with the boundary of P. We show that without a priori knowledge of what the models look like, no finite number of finger probes will suffice to localize the point p. When the models are given in advance, we give both batch and dynamic probing strategies for solving the problem. We consider both the case where the models are aligned rectilinear polygons and the case where the models are simple polygons.
Access to the requested content is limited to institutions that have purchased or subscribe to SPIE eBooks.
You are receiving this notice because your organization may not have SPIE eBooks access.*
*Shibboleth/Open Athens users─please
sign in
to access your institution's subscriptions.
To obtain this item, you may purchase the complete book in print or electronic format on
SPIE.org.
INSTITUTIONAL Select your institution to access the SPIE Digital Library.
PERSONAL Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.