Search

In video games and robotics, one often discretizes a continuous 2D environment into a regular grid with blocked and unblocked cells and then finds shortest paths for the agents on the resulting grid graph. Shortest grid paths, of course, are not necessarily true shortest paths in the continuous 2D environment. In this article, we therefore study how much longer a shortest grid path can be than a corresponding true shortest path on all regular grids with blocked and unblocked cells that tessellate continuous 2D environments. We study 5 different vertex connectivities that result from both different tessellations and different definitions of the neighbors of a vertex. Our path-length analysis yields either tight or asymptotically tight worst-case bounds in a unified framework. Our results show that the percentage by which a shortest grid path can be longer than a corresponding true shortest path decreases as the vertex connectivity increases. Our path-length analysis is topical because it determines the largest path-length reduction possible for any-angle path-planning algorithms (and thus their benefit), a class of path-planning algorithms in artificial intelligence and robotics that has become popular.

The multinomial selection problem is to find a stopping policy for repeated independent trials, each of which reports a winner among competing alternatives that has low expected cost and high probability of correct selection (PCS) of the best alternative. In 1959, Bechhofer, Elmaghraby, and Morse formulated the problem as minimizing the worst-case expected number of trials, subject to a lower bound on PCS and upper bound on the maximum number of trials, over all probability vectors outside an indifference zone. For the case of two alternatives, we prove that if one employs a particular probability vector known as the slippage configuration, then a linear program always finds an optimal stopping policy.

The yolk, an important concept of spatial majority voting theory, is assumed to be unique when the number of individuals is odd. We prove that this claim is true in $$ {\mathbb {R}} ^{2}$$ but false in $$ {\mathbb {R}} ^{3}$$ , and discuss the differing implications of non-uniqueness from the normative and predictive perspectives.

Serial section transmission electron microscopy (ssTEM) is the most promising tool for investigating the three-dimensional anatomy of the brain with nanometer resolution. Yet as the field progresses to larger volumes of brain tissue, new methods for high-yield, low-cost, and high-throughput serial sectioning are required. Here, we introduce LASSO (Loop-based Automated Serial Sectioning Operation), in which serial sections are processed in "batches." Batches are quantized groups of individual sections that, in LASSO, are cut with a diamond knife, picked up from an attached waterboat, and placed onto microfabricated TEM substrates using rapid, accurate, and repeatable robotic tools. Additionally, we introduce mathematical models for ssTEM with respect to yield, throughput, and cost to access ssTEM scalability. To validate the method experimentally, we processed 729 serial sections of human brain tissue (~40 nm x 1 mm x 1 mm). Section yield was 727/729 (99.7%). Sections were placed accurately and repeatably (x-direction: -20 ± 110 μm (1 s.d.), y-direction: 60 ± 150 μm (1 s.d.)) with a mean cycle time of 43 s ± 12 s (1 s.d.). High-magnification (2.5 nm/px) TEM imaging was conducted to measure the image quality. We report no significant distortion, information loss, or substrate-derived artifacts in the TEM images. Quantitatively, the edge spread function across vesicle edges and image contrast were comparable, suggesting that LASSO does not negatively affect image quality. In total, LASSO compares favorably with traditional serial sectioning methods with respect to throughput, yield, and cost for large-scale experiments, and represents a flexible, scalable, and accessible technology platform to enable the next generation of neuroanatomical studies.

In the aftermath of a flood, fire ants, Solenopsis invicta , cluster into temporary encampments. The encampments can contain hundreds of thousands of ants and reach over 30 ants high. How do ants build such tall structures without being crushed? In this combined experimental and theoretical study, we investigate the shape and rate of construction of ant towers around a central support. The towers are bell shaped, consistent with towers of constant strength such as the Eiffel tower, where each element bears an equal load. However, unlike the Eiffel tower, the ant tower is built through a process of trial and error, whereby failed portions avalanche until the final shape emerges. High-speed and novel X-ray videography reveal that the tower constantly sinks and is rebuilt, reminiscent of large multicellular systems such as human skin. We combine the behavioural rules that produce rafts on water with measurements of adhesion and attachment strength to model the rate of growth of the tower. The model correctly predicts that the growth rate decreases as the support diameter increases. This work may inspire the design of synthetic swarms capable of building in vertical layers.

Performance guarantees for multinomial selection procedures are usually derived by finding the least favorable configuration (LFC)—the one for which the probability of correct selection is minimum outside the indifference zone—and then evaluating the procedure on that configuration. The slippage configuration has been proved to be the LFC for several procedures and has been conjectured to be the worst for some other procedures. The principal result of this article unifies and extends all previous results for two alternatives: the slippage configuration is the worst for all procedures that have a finite expected number of trials and always select the alternative with more successes. A generalization of the key inequality in the proof to an arbitrary number of alternatives is conjectured.

Multinomial selection is concerned with selecting the most probable (best) multinomial alternative. The alternatives compete in a number of independent trials. In each trial, each alternative wins with an unknown probability specific to that alternative. A long-standing research goal has been to find a procedure that minimizes the expected number of trials subject to a lower bound on the probability of correct selection ( (CS)). Numerous procedures have been proposed over the past 55 years, all of them suboptimal, for the version where the number of trials is bounded. We achieve the goal in the following sense: For a given multinomial probability vector, lower bound on (CS), and upper bound on trials, we use linear programming (LP) to construct a procedure that is guaranteed to minimize the expected number of trials. This optimal procedure may necessarily be randomized. We also present a mixed-integer linear program (MIP) that produces an optimal deterministic procedure. In our computational stud...

To survive floods, fire ants link their bodies together to build waterproof rafts. Such rafts can be quite large, exceeding 100,000 individuals in size. In this study, we make two improvements on a previously reported model on the construction rate of rafts numbering between 3,000 and 10,000 individuals. That model was based upon experimental observations of randomly-directed linear ant trajectories atop the raft. Here, we report anomalous behavior of ants atop larger rafts of up to 23,000 ants. As rafts increase in size, the behavior of ants approaches diffusion, which is in closer alignment with other studies on the foraging and scouting patterns of ants. We incorporate this ant behavior into the model. Our modified model predicts more accurately the growth of large rafts. Our previous model also relied on an assumption of raft circularity. We show that this assumption is not necessary for large rafts, because it follows from the random directionality of the ant trajectories. Our predicted relationship between raft size and circularity closely fits experimental data.

We study the classical edge-searching pursuit-evasion problem where a number of pursuers have to clear a given graph of fast-moving evaders despite poor visibility, for example, where robots search a cave system to ensure that no terrorists are hiding in it. We study when polynomial-time algorithms exist to determine how many robots are needed to clear a given graph (minimum robot problem) and how a given number of robots should move on the graph to clear it with either a minimum sum of their travel distances (minimum distance problem) or minimum task-completion time (minimum time problem). The robots cannot clear a graph if the vertex connectivity of some part of the graph exceeds the number of robots. Researchers therefore focus on graphs whose subgraphs can always be cut at a limited number of vertices, that is, graphs of low treewidth, typically trees. We describe an optimal polynomial-time algorithm, called CLEARTHETREE, that is shorter and algorithmically simpler than the state-of-the-art algorithm for the minimum robot problem on unit-width unit-length trees. We then generalize prior research to both unit-width arbitrary-length and unit-length arbitrary-width graphs and derive both algorithms and time complexity results for a variety of graph topologies. Pursuit-evasion problems on the former graphs are generally simpler than pursuit-evasion problems on the latter graphs. For example, the minimum robot and distance problems are solvable in polynomial time on unit-width arbitrary-length trees but NP-hard on unit-length arbitrary-width trees.

The finagle point, the epsilon-core, and the yolk are all predictors of majority-rule decision-making in spatial voting models. These predictors each minimize a radius needed in some sense to alter preferences so as to achieve stability. Brauninger showed that the finagle radius is never smaller than the epsilon-core radius, and claimed that the finagle point is within the epsilon core. This article shows that the finagle radius is sandwiched in between the epsilon-core and yolk radii, and that there is a significant logical gap in Brauninger’s proof that the finagle point is within the epsilon-core. This article also examines Brauninger’s other conclusions in view of an inaccurate computation of the yolk, and shows that they are valid all the more so.

The classic instability theorems of Euclidean voting theory definitively treat all cases except that of an even number of voters in two dimensions. For that case, all that has been known is that the set of stable configurations is neither measure 0 nor measure 1. We prove that instability occurs with probability converging rapidly to 1 as the population increases.

Localization, which is the determination of one's location in a known terrain, is a fundamental task for autonomous robots. This paper presents several new basic theoretical results about localization. We show that, even under the idealized assumptions of accurate sensing and perfect actuation, it is intrinsically difficult to localize a robot with a travel distance that is close to minimal. Our result helps to theoretically justify the common use of fast localization heuristics, such as greedy localization, which always moves the robot to a closest informative location (where the robot makes an observation that decreases the number of its possible locations). We show that the travel distance of greedy localization is much larger than minimal in some terrains because the closest informative location can distract greedy localization from a slightly farther, but much more informative, location. However, we also show that the travel distance of greedy localization can be larger, but not much larger, than the terrain size n. Thus, the travel distance of greedy localization scales well with the terrain size and is much larger than minimal in some terrains, not because it is large with respect to the terrain size, but because the minimal travel distance is exceptionally small in these terrains. As a corollary to our analysis, we show that the travel distance of greedy mapping (which always moves the robot to a closest location, where it makes an observation that increases its knowledge of the terrain) cannot be much larger than the terrain size. In theoretical terms, we prove the NP-hardness of minimization of travel distance for localization to within a logarithmic factor of the terrain size. We prove that the travel distance of greedy localization is at least order n/ log2 n larger than minimal in some terrains and that it is at least order n log n / log log n in the worst case. Finally, we prove that the travel distance of both greedy localization and greedy mapping is at most order n log n. Previously, it was only known that it is NP-hard to localize with minimal travel distance and that the travel distances of greedy localization and greedy mapping are at most order n 3/2.

This paper focuses on the well-known Diaz and O'Rourke [M. Diaz and J. O'Rourke, Algorithms for computing the center of area of a convex polygon, Visual Comput. 10 (1994), 432-442.] iterative search algorithm to find the Simpson Point of a market, described by a convex polygon. In their paper, they observed that their algorithm did not appear to converge pointwise, and therefore, modified it to do so. We first present an enhancement of their algorithm that improves its time complexity from O(log2e) to O(n log 1/e). This is then followed by a proof of pointwise convergence and derivation of explicit bounds on convergence rates of our algorithm. It is also shown that with an appropriate interpretation, our convergence results extend to all similar iterative search algorithms to find the Simpson Point-a class that includes the original unmodified Diaz-O'Rourke algorithm. Finally, we explore how our algorithm and its convergence guarantees might be modified to find the Simpson Point when the demand distribution is non-uniform.

Democratic simple majority voting is perhaps the most widely used method of group decision making in our time. Standard theory, based on “instability” theorems, predicts that a group employing this method will almost always fail to reach a stable conclusion. But empirical observations do not support the gloomy predictions of the instability theorems. We show that the instability theorems are themselves unstable in the following sense: if the model of voter behavior is altered however slightly to incorporate any of the several plausible characteristics of decision making, then the instability theorems do not hold and in fact the probability of stability converges to 1 as the population increases, when the population is sampled from a centered distribution. The assumptions considered include: a cost of change; bounded rationality; perceptual thresholds; a discrete proposal space, and others. Evidence from a variety of fields justifies these assumptions in all or most circumstances. One consequence of this work is to render precise and rigorous, the solution proposed by Tullock to the impossibility problem. All of the stability results given here hold for an arbitrary dimension. We generalize the results to establish stability with probability converging to 1 subject to trade-offs between the assumptions and the degree of non-centeredness of the population. We also extend the results from Euclidean preferences to the more general class of intermediate preferences.

The yolk, defined by McKelvey as the smallest ball intersecting all median hyperplanes, is a key concept in the Euclidean spatial model of voting. Koehler conjectured that the yolk radius of a random sample from a uniform distribution on a square tends to zero. The following sharper and more general results are proved here: Let the population be a random sample from a probability measure μ on ℜ m . Then the yolk of the sample does not necessarily converge to the yolk of μ . However, if μ is strictly centered, i.e. the yolk radius of μ is zero, then the radius of the sample yolk will converge to zero almost surely, and the center of the sample yolk will converge almost surely to the center of the yolk of μ . Moreover, if the yolk radius of μ is nonzero, the sample yolk radius will not converge to zero if μ contains three non-collinear mass points or if somewhere it has density bounded away from zero in some ball of positive volume. All results hold for both odd and even population sizes.

Define the predictability number α(T) of a tournament T to be the largest supermajority threshold \({\frac{1}{2} < \alpha\leq 1}\) for which T could represent the pairwise voting outcomes from some population of voter preference orders. We establish that the predictability number always exists and is rational. Only acyclic tournaments have predictability 1; the Condorcet voting paradox tournament has predictability \({\frac{2}{3}}\); Gilboa has found a tournament on 54 alternatives (i.e. vertices) that has predictability less than \({\frac{2}{3}}\) , and has asked whether a smaller such tournament exists. We exhibit an 8-vertex tournament that has predictability \({\frac{13}{20}}\) , and prove that it is the smallest tournament with predictability < \({\frac{2}{3}}\) . Our methodology is to formulate the problem as a finite set of two-person zero-sum games, employ the minimax duality and linear programming basic solution theorems, and solve using rational arithmetic.

Fast algorithms can be created for many graph problems when instances are confined to classes of graphs that are recursively constructed. This article first describes some basic conceptual notions regarding the design of such fast algorithms, and then the coverage proceeds through several recursive graph classes. Specific classes include trees, series-parallel graphs, k -terminal graphs, treewidth- k graphs, k -trees, partial k -trees, k -jackknife graphs, pathwidth- k graphs, bandwidth- k graphs, cutwidth- k graphs, branchwidth- k graphs, Halin graphs, cographs, cliquewidth- k graphs, k -NLC graphs, k -HB graphs, and rankwidth- k graphs. The definition of each class is provided. Typical algorithms are applied to solve problems on instances of most classes. Relationships between the classes are also discussed.

Localization is a fundamental problem in robotics. The “kidnapped robot” possesses a compass and map of its environment; it must determine its location at a minimum cost of travel distance. The problem is NP-hard [G. Dudek, K. Romanik, and S. Whitesides, SIAM J. Comput., 27 (1998), pp. 583-604] even to minimize within factor $c\log n$ [C. Tovey and S. Koenig, Proceedings of the National Conference on Artificial Intelligence, Austin, TX, 2000, pp. 819-824], where $n$ is the map size. No approximation algorithm has been known. We give an $O(\log^3n)$-factor algorithm. The key idea is to plan travel in a “majority-rule” map, which eliminates uncertainty and permits a link to the $\frac{1}{2}$-Group Steiner (not Group Steiner) problem. The approximation factor is not far from optimal: we prove a $c\log^{2-\epsilon}n$ lower bound, assuming $NP\not\subseteq ZTIME(n^{polylog(n)})$, for the grid graphs commonly used in practice. We also extend the algorithm to polygonal maps by discretizing the problem using novel geometric techniques.

We exhibit a polar relationship between two measures that have been proposed to evaluate the importance of TSP facets, the Kuhn–Gomory shooting experiment size and the probability of integrality in an augmented LP relaxation. The polarity establishes the complexity of performing the shooting experiment. We illustrate the resulting relationship on the Chinese postman and minimum spanning set problems.

One explanation for a positive correlation between environmental and financial performance at the firm level is a bias in firms' investment evaluation processes caused by systematic differences between environmental and other investment opportunities. One of these systematic differences, often hypothesized but still unverified, is that environmental costs occur farther in the future than other costs. We empirically test this hypothesis, and find statistically significant support for it. In our data set the mean time lag for environmental costs was more than ten years, compared with five years for the control set costs. Such a difference could induce managers to accept too much environmental liability if they evaluate investments using discounted cash flow methods with a discount rate based on the firm-wide cost of capital. Copyright © 2006 John Wiley & Sons, Ltd and ERP Environment.

Given a class Γ of curves in [0, 1]2, we ask: in a cloud of n uniform random points, how many points can lie on some curve γ ∈ Γ? Classes studied here include curves of length less than or equal to L, Lipschitz graphs, monotone graphs, twice-differentiable curves, and graphs of smooth functions with m-bounded derivatives. We find, for example, that there are twice-differentiable curves containing as many as O P (n 1/3) uniform random points, but not essentially more than this. More generally, we consider point clouds in higher-dimensional cubes [0, 1] d and regular hypersurfaces of specified codimension, finding, for example, that twice-differentiable k-dimensional hypersurfaces in R d may contain as many as O P (n k/(2d-k)) uniform random points. We also consider other notions of ‘incidence’, such as curves passing through given location/direction pairs, and find, for example, that twice-differentiable curves in R 2 may pass through at most O P (n 1/4) uniform random location/direction pairs. Idealized applications in image processing and perceptual psychophysics are described and several open mathematical questions are identified for the attention of the probability community.

D* is a greedy heuristic planning method that is widely used in robotics, including several Nomad class robots and the Mars rover prototype, to reach a destination in unknown terrain. We obtain nearly sharp lower and upper bounds of $\Omega(n\log n/\log\log n)$ and O(n log n), respectively, on the worst-case total distance traveled by the robot, for the grid graphs on n vertices typically used in robotics applications. For arbitrary graphs we prove an O(n log2 n) upper bound.

Internet centers host services for e-banks, e-auctions and other clients. Hosting centers then must allocate servers among clients to maximize revenue. The limited number of servers, costs of reallocating servers, and unpredictability of requests make server allocation optimization difficultBased on the many similarities between server and honey bee colony forager allocation, we pro pose a new decentralized honey bee algorithm which dynamically allocates servers to satisfy request loads. We compare it against an omniscient optimality algorithm, a conventional greedy algorithm, and an algorithm that computes omnisciently the optimal static allocation. We evaluate performance on simulated request streams and commercial trace dataOur algorithm performs better than static or greedy for highly variable request loads, but greedy can outperform it under low variability. Honey bee forager allocation, though suboptimal for static food sources, may possess a counterbalancing responsiveness to food source variability.

This paper evaluates the cost savings achievable in the infinite horizon single-asset replacement problem by considering technological progress affecting assets available after multiple future replacements and allowing variable service lives. Using a simple geometric model to specify asset costs, constant service lives are shown to be suboptimal. It is shown by example that common replacement decision methods yield higher service lives for the first asset and substantially different discounted total costs for the series of assets. This effect is illustrated numerically using automobile cost data.

Planning in nondeterministic domains is typically intractable due to the large number of contingencies. Two techniques for speeding up planning in nondeterministic domains are agent-centered search and assumption-based planning. Both techniques interleave planning in deterministic domains with plan execution. They differ in how they make planning deterministic. To determine how suboptimal their plans are, we study two planning methods for robot navigation in initially unknown terrain that have successfully been used on mobile robots but not been analyzed before. The planning methods differ both in the technique they use to speed up planning and in the robot-navigation task they solve. Greedy Mapping uses agent-centered search to map unknown terrain. Dynamic A∗ uses assumption-based planning to navigate to a given goal location in unknown terrain. When we formalize abstractions of these planning methods on undirected graphs G=(V,E), they turn out to be similar enough that we are able to analyze their travel distance in a unified way. We discover that neither method is optimal in a worst-case sense, by a factor of Ω(log|V|/loglog|V|). We also derive factor O(|V|) upper bounds to show that these methods are not very badly sub-optimal in this sense. These results provide a first step towards explaining the good empirical results that have been reported about Greedy Mapping and Dynamic A∗ in the experimental literature. More generally, they show how to use tools from graph theory to analyze the plan quality of practical planning methods for nondeterministic domains.

We consider a very general online scheduling problem with an objective to minimize the maximum level of resource allocated. We find a simple characterization of an optimal deterministic online algorithm. We develop further results for the two, more specific problems of single resource scheduling and hierarchical line balancing. We determine how to compute optimal online algorithms for both problems using linear programming and integer programming, respectively. We show that randomized algorithms can outperform deterministic algorithms, but only if the amount of work done is a nonconcave function of resource allocation.

Coalitions of weighted voting games can be restricted to be connected components of a graph. As a consequence, coalition formation, and therefore a player’s power, depends on the topology of the graph. We analyze the problems of computing the Banzhaf and the Shapley–Shubik power indexes for this class of voting games and prove that calculating them is #P-complete in the strong sense for general graphs. For trees, we provide pseudo-polynomial time algorithms and prove #P-completeness in the weak sense for both indexes.

Computational complexity measures how much work is required to solve different problems. It provides a useful classification tool for OR/MS practitioners, especially when tackling discrete deterministic problems. Use it to tell, in advance, whether a problem is easy or hard. Knowing this won't solve your problem, but it will help you to decide what kind of solution method is appropriate. Complexity analysis helps you to understand and deal with hard problems. It can pinpoint the nasty parts of your problem, alert you to a special structure you can take advantage of, and guide you to model more effectively. You will solve your problem better when you know the borders between hard and easy. Locating the difficulty can indicate where to aggregate, decompose, or simplify. To detect and prove computational difficulty, show that a known hard problem from the literature is embedded within your problem. Fix parameters of your problem to arrive at the known hard problem, or use specialization, padding, forcing, or the more difficult gadget proofs. Study contrasting pairs of easy and hard problems to develop your intuitive ability to assess complexity.