The Freeze-Tag Problem: How to Wake Up a Swarm of Robots

An optimization problem that naturally arises in the study of swarm robotics is the Freeze-Tag Problem (FTP) of how to awaken a set of "asleep" robots, by having an awakened robot move to their locations. Once a robot is awake, it can assist in awakening other slumbering robots. The objective is to have all robots awake as early as possible. While the FTP bears some resemblance to problems from areas in combinatorial optimization such as routing, broadcasting, scheduling, and covering, its algorithmic characteristics are surprisingly different. We consider both scenarios on graphs and in geometric environments. In graphs, robots sleep at vertices and there is a length function on the edges. Awake robots travel along edges, with time depending on edge length. For most scenarios, we consider the offline version of the problem, in which each awake robot knows the position of all other robots. We prove that the problem is NP-hard, even for the special case of star graphs. We also establish hardness of approximation, showing that it is NP-hard to obtain an approximation factor better than 5/3, even for graphs of bounded degree. These lower bounds are complemented with several positive algorithmic results, including: · We show that the natural greedy strategy on star graphs has a tight worst-case performance of 7/3 and give a polynomial-time approximation scheme (PTAS) for star graphs. · We give a simple O(log δ)-competitive online algorithm for graphs with maximum degree δ and locally bounded edge weights. · We give a PTAS, running in nearly linear time, for geometrically embedded instances.     

Keith Devlin,Goodbye, Descartes: The End of Logic and the Search for a New Cosmology of the Mind

Minds and Machines -     

Analogical Problem Solving in Casual and Experienced Users: When Interface Consistency Leads to Inappropriate Transfer

ABSTRACT

The problem-solving abilities of casual users were compared to experienced users in a computer setting. It was hypothesized that casual users would benefit from reduced consistency with other applications. Experience was gauged with a questionnaire and empirical measures. Four interfaces were developed with varying degrees of similarity to Web browsers. Using a Web browser as a source problem, participants were tested with two of the experimental interfaces. The data indicated that the accuracy of casual users was equivalent across consistent and inconsistent interfaces but that the consistent interfaces had significantly higher latencies. The primary conclusions of the study are that performance for casual users is improved by superficially inconsistent interfaces and that their performance is equivalent to experienced users when a true analogue is present. Commonalities with familiar elements may be a hindrance.     

How to Solve a Cubic Equation, Part 2: The 11 Case

Jim Blinn discusses a good practical closed-form solution process for cubic equations and makes some observations about the relation between iterative and closed-form solutions.     

How to Solve a Cubic Equation, Part 4: The 111 Case

It should not be surprising that in solving cubic equations, sooner or later you are going to have to take the cube root of something. But it's not immediately obvious what cubic equations have to do with arc cosines. Well, in the general case of complex coefficients and roots we would need to take the cube root of a complex number     

The Gatekeeper's Guide, or How to Kill a Tool

Over the past few decades, new tools that facilitate the cost-effective production of high-quality software have slowly gained ground. The following guidelines show how you can push any tool to the side, perpetuating the manual methods that have always worked in the past     

How to clear a block: A theory of plans

Problems in commonsense and robot planning are approached by methods adapted from program synthesis research; planning is regarded as an application of automated deduction. To support this approach, we introduce a variant of situational logic, called plan theory, in which plans are explicit objects.A machine-oriented deductive-tableau inference system is adapted to plan theory. Equations and equivalences of the theory are built into a unification algorithm for the system. Frame axioms are built into the resolution rule.Special attention is paid to the derivation of conditional and recursive plans. Inductive proofs of theorems for even the simplest planning problems, such as clearing a block, have been found to require challenging generalizations.This research was supported by the National Science Foundation under Grants DCR-82-14523 and DCR-85-12356, by the Defense Advanced Research Projects Agency under Contract N00039-84-C-0211, by the United States Air Force Office of Scientific Research under Contract AFOSR-85-0383, by the Office of Naval Research under Contract N00014-84-C-0706, by United States Army Research under Contract DAJA-45-84-C-0040, and by a contract from the International Business Machines Corporation.Preliminary versions of parts of this paper were presented at the Eighth International Conference on Automated Deduction, Oxford, England, July 1986, and the Workshop on Planning and Reasoning about Actions, Timberline, Oregon, July 1986.     

How to make a best-seller: Optimal product design problems

We formalize and analyze the computational complexity of three problems which are at the keystone of any marketing management process. Given the preferences of customers over the attribute values we may assign to our product (i.e. its possible features), the attribute values of products sold by our competitors, and which attribute values are available to each producer (due to e.g. technological limitations, legal issues, or availability of resources), we consider the following problems: (a) select the attributes of our product in such a way that the number of customers is maximized; (b) find out whether there is a feasible strategy guaranteeing that, at some point in the future before some deadline, we will reach a given average number of customers during some period of time; and (c) the same question as (b), though the number of steps before the deadline is restricted to be, at most, the number of attributes. We prove that these problems are Poly-APX-complete, EXPTIME-complete, and PSPACE-complete, respectively. After presenting these theoretical properties, heuristic methods based on genetic, swarm and minimax algorithms are proposed to suboptimally solve these problems. We report experimental results where these methods are applied to solve some artificially-designed problem instances, and next we present a case study, based on real data, where these algorithms are applied to a particular kind of product: we automatically design the political platform of a political party to maximize its numbers of votes in an election (problem (a)) and its number of supporters along time (problems (b) and (c)). The problem instances solved in this case study are constructed from publicly released polls on political tendencies in Spain.     

When to jump in: The role of the instructor in online discussion forums

As asynchronous discussion forums become more prevalent in online and flexible-delivery modes of teaching, understanding the role that instructors play in student learning in these forums becomes an important issue. Whether the instructor chooses to lead discussions or to keep a low profile can affect student participation in surprising ways. In this study, we investigate how instructor participation rates, the timing of instructor postings (during or at the end of a forum) and nature of their postings (questions, answers or a mix of the two) relate to student participation and perception.     

How to draw a sphere. 3. The hyperbolic horizon

We want to draw a sphere. Actually, we want to draw an arbitrarily scaled and oriented ellipsoid. In part one I showed some matrix algebra for describing, transforming, and intersecting points, planes, and quadric surfaces (which include spheres). In part two I defined some useful coordinate systems and transformations. With the proper handling of hyperbolic silhouette curves the program works for any sphere (or ellipsoid) viewed from any point and in any direction. Making the algorithm work properly seems to be mostly a game of minus sign management since most of the tests hinge on the sign of some quantity. I've spent many hours chasing down rogue minus signs. The only thing left to discuss are some antialiasing tricks     

How to Solve a Cubic Equation, Part 5: Back to Numerics

In the previous four columns, the properties of the homogeneous cubic polynomial were studied. In this article, the author introduces two new algorithms that, at first, look quite different from what we've done so far. It will turn out, though, that they actually do fit into our solution scheme. In showing this, he has taken good ideas from a variety of authors and translated them into a common notation while also converting them to deal with homogeneous polynomials     

From SOS Specifications to Structured Coalgebras: How to Make Bisimulation a Congruence

In this paper we address the issue of providing a structured coalgebra presentation of transition systems with algebraic structure on states determined by an equational specification Γ. More precisely, we aim at representing such systems as coalgebras for an endofunctor on the category of Γ-algebras. The systems we consider are specified by using a quite general format of SOS rules, the algebraic format, which in general does not guarantee that bisimilarity is a congruence.We first show that the structured coalgebra representation works only for systems where transitions out of complex states can be derived from transitions out of corresponding component states. This decomposition property of transitions indeed ensures that bisimilarity is a congruence. For a system not satisfying this requirement, next we propose a closure construction which adds context transitions, i.e., transitions that spontaneously embed a state into a bigger context or vice-versa. The notion of bisimulation for the enriched system coincides with the notion of dynamic bisimilarity for the original one, that is, with the coarsest bisimulation which is a congruence. This is sufficient to ensure that the structured coalgebra representation works for the systems obtained as result of the closure construction.     

How Not to Be Seen II: The Defenders Fight Back

For pt.I see ibid., vol. 5, no.1, p.67-69 (2007). This article discusses about stealthy software-that is, software that manipulates a computer in some way to avoid some aspect of its operation. The stealth is divided up into roughly three categories: passive, hooking, and hypervisor-based stealth detection. Most stealth malware hides by hooking and redirecting system calls, either at the kernel or the operating system (OS) level.     

How to detect a counterfeit coin: Adaptive versus non-adaptive solutions

In an old weighing puzzle, there are n?3 coins that are identical in appearance. All the coins except one have the same weight, and that counterfeit one is a little bit lighter or heavier than the others, though it is not known in which direction. What is the smallest number of weighings needed to identify the counterfeit coin and to determine its type, using balance scales without measuring weights? This question was fully answered in 1946 by Dyson [The Mathematical Gazette 30 (1946) 231-234]. For values of n that are divisible by three, Dyson's scheme is non-adaptive and hence its later weighings do not depend on the outcomes of its earlier weighings. For values of n that are not divisible by three, however, Dyson's scheme is adaptive. In this note, we show that for all values n?3 there exists an optimal weighing scheme that is non-adaptive.     

Building a Quantum Network: How to Optimize Security and Expenses

Quantum key distribution (QKD) is regarded as a key-technology for the upcoming decades. Its practicability has been demonstrated through various experimental implementations. Wide-area QKD networks are a natural next step and should inherit the selling point of provable security. However, most research in QKD focuses on point-to-point connections, leaving end-to-end security to the trustworthiness of intermediate repeater nodes, thus defeating any formal proof of security: why bother outwitting QKD, if the repeater node is an easy prey, and an equally valuable target? We discuss methods of designing QKD networks with provable end-to-end security at provably optimized efforts. We formulate two optimization problems, along with investigations of computational difficulty: First, what is the minimal cost for a desired security? Second, how much security is achievable under given (budget-)constraints? Both problems permit applications of commercial optimization software, so allow taking a step towards an economic implementation of a globally spanning QKD network.     

How to facilitate inter-organizational knowledge sharing: The impact of trust

In this era of the network economy, inter-organizational knowledge sharing is one key driving force required to streamline value chain activities and maximize operational benefits. Knowledge sharing can be realized when the involved business partners successfully develop trust and build long-term partnerships. In this study, a model of knowledge sharing across the supply chain is constructed. Factors such as shared goals, social relational embeddedness, and influence strategy are investigated to determine whether they act as major driving forces to develop inter-organizational trust among the various supply chain members. The survey is based on 226 managers located in major industrial parks in Taiwan; the results suggest that trust is enforced when organizations develop shared goals, form social relational embeddedness, and initiate influence strategies. In addition, inter-organizational trust leads to better inter-organizational collaboration and knowledge sharing. Theoretical and practical implications are also discussed.     

Online group work patterns: How to promote a successful collaboration

Participation is a complex process, engaging the whole person, implying cognitive, emotional and relational aspects. In online open and distant learning, group work is a commonly used strategy, given its collaborative nature and constructivist framework (2, 4 and 7). In this context, collaborative learning processes are highly dependent on the shared written information and the interactions that are established among the participants. The types of interactions that occur within such groups can influence their knowledge convergence processes, and are often decisive for its success.     

Scheduling training for a tank battalion: How to measure readiness

This paper shows how to measure the readiness for a military unit, with the example of a tank battalion. We first show that training readiness can be measured by the minimum makespan of the training schedule. We call this the train-up problem. Second, the effect of a peacetime budget on the training readiness can be calculated by solving the readiness budget problem. Third, the resources required for training can be determined with the readiness capacity problem. To solve these problems, we give a dynamic program (DP) for one unit such as a company, and a column generation algorithm for an aggregate unit such as a battalion.