Wayne and Layne

Two Generals’ Problem

In computing, the Two Generals’ Problem is a thought experiment meant to illustrate the pitfalls and design challenges of attempting to coordinate an action by communicating over an unreliable link. It is related to the more general Byzantine Generals’ Problem (though published long before that later generalization) and appears often in introductory classes about computer networking (particularly with regards to the Transmission Control Protocol), though it can also apply to other types of communication. Some authors also refer to this as the Two Army Problem or the Coordinated Attack Problem.

via Two Generals’ Problem – Wikipedia, the free encyclopedia.

Proportional navigation

Proportional navigation is a guidance law used in some form or another by most homing air target missiles. It is based on the fact that two vehicles are on a collision course when their direct Line-of-Sight does not change direction. PN dictates that the missile velocity vector should rotate at a rate proportional to the rotation rate of the line of sight and in the same direction.

An = N' * L' * V

Where An is the acceleration perpendicular to missile velocity vector, N’ is the proportionality constant (dimensionless), L’ is the line of sight rate, and V is the velocity.

For example, if the line of sight rotates slowly from north to east, the missile should turn to the right by a certain factor faster than the LOS-rate. This factor is called the Navigation Constant K_nav.

via Proportional navigation – Wikipedia, the free encyclopedia.

Ant Colony Optimization

The ant colony optimization algorithm (ACO), is a probabilistic technique for solving computational problems which can be reduced to finding good paths through graphs.

In the real world, ants initially wander randomly, and upon finding food return to their colony while laying down pheromone trails. If other ants find such a path, they are likely not to keep traveling at random, but to instead follow the trail, returning and reinforcing it if they eventually find food. Over time, however, the pheromone trail starts to evaporate, thus reducing its attractive strength. The more time it takes for an ant to travel down the path and back again, the more time the pheromones have to evaporate. A short path, by comparison, gets marched over faster, and thus the pheromone density remains high as it is laid on the path as fast as it can evaporate. Pheromone evaporation has also the advantage of avoiding the convergence to a locally optimal solution. If there were no evaporation at all, the paths chosen by the first ants would tend to be excessively attractive to the following ones. In that case, the exploration of the solution space would be constrained.Thus, when one ant finds a good i.e., short path from the colony to a food source, other ants are more likely to follow that path, and positive feedback eventually leads all the ants following a single path. The idea of the ant colony algorithm is to mimic this behavior with “simulated ants” walking around the graph representing the problem to solve.

via Ant colony optimization – Wikipedia, the free encyclopedia.

The Aggregate Magic Algorithms

A useful and interesting collection of low-level algorithms in C and assembly.

The Aggregate Magic Algorithms – There are lots of people and places that create and collect algorithms of all types. Unfortunately, in building systems hardware and software, we in The Aggregate often have found it necessary to do relatively obscure low-level things very efficiently. Many of the tricks we’ve devised or collected either require assembly language coding or are not entirely portable when coded in HLLs like C, but these techniques are still valuable because they can yield significant performance improvements over the more obvious ways of doing things.

via The Aggregate Magic Algorithms.

asprintf

Over a year ago, I created a new function called sprintfAlloc that was like sprintf, except it printed into and returned a newly-allocated chunk of memory. For more details, check out the original post.

In my travels since then, I’ve run across another function, in the GNU C library, that does the same thing. This function is called asprintf, and has this signature:

int asprintf(char** ret, const char* format, ...);

For more information, check out the manual page.

Rosenbrock’s Banana Function

In mathematical optimization, Rosenbrock’s Banana Function is a non-convex function used as a test problem for optimization algorithms.

This function is often used to test performance of optimization algorithms. The global minimum is inside a long, narrow, parabolic shaped flat valley. To find the valley is trivial, however to converge to the global minimum is difficult.

It is defined by

f(x, y) = (1 – x)^2 + 100(y – x^2)^2

It has a global minimum at (x, y) = (1, 1) where f(x, y) = 0. A different coefficient of the second term is sometimes given, but this does not affect the position of the global minimum.

Rosenbrock 's Banana Function

via Rosenbrock function – Wikipedia, the free encyclopedia.

QuickCG

When working with Java or (I presume) .NET, there is a standard, built-in way to do 2-dimensional graphics, such as drawing pixels or shapes on a blank canvas. These built-in graphics systems are very nice for displaying your own custom charts or graphs of the data being worked with, for example, plotting the lifetime of a human trying to escape from velociraptors.

When programming in C or C++, there isn’t a standard way to do graphics, at least none that I am aware of. During my final semester at the University of Minnesota, I took a robotics class that required us to program the robots in a C++ environment. The robots we were using all had SICK laser scanners, and we wanted to plot the raw laser-data so that we could ensure that everything was working correctly.

While trying to find a decently simple way to make 2D drawings from C/C++, we discovered a very simple graphics library called QuickCG, which is a very thin wrapper around the standard SDL (Simple DirectMedia Layer) libraries. This package (actually it’s only a source and header file) includes examples and good documentation on the project website, and is extremely easy to use.

more »

Java Code Profiling

Here is a very small Java class to help time function calls or sections of code. Of course, it won’t be exactly right on (due to scheduling issues, etc), but it’s pretty good at helping with initial profiling and performance measurements.


public class Stopwatch
{
    private long start;
    private long stop;
    
    public void start()
    {
        // start timing
        start = System.currentTimeMillis();
    }
    
    public void stop()
    {
        // stop timing
        stop = System.currentTimeMillis();
    }
    
    public long elapsedTimeMillis()
    {
        return stop - start;
    }
    
    public String toString()
    {
        // print execution time
        return "elapsedTimeMillis: " + Long.toString(elapsedTimeMillis());
    }
}


Quorum Sensing

Quorum sensing is a type of decision-making process used by decentralized groups to coordinate behavior. Many species of bacteria use quorum sensing to coordinate their gene expression according to the local density of their population. Similarly, some social insects use quorum sensing to make collective decisions about where to nest. In addition to its function in biological systems, quorum sensing has several useful applications for computing and robotics.

Quorum sensing can function as a decision-making process in any decentralized system, as long as individual components have (a) a means of assessing the number of other components they interact with and (b) a standard response once a threshold number of components is detected.

One totally awesome example of quorum sensing:

Colonies of the ant Temnothorax albipennis nest in small crevices between rocks. When the rocks shift and the nest is broken open, these ants must quickly choose a new nest to move into. During the first phase of the decision-making process, a small portion of the workers leave the destroyed nest and search for new crevices. When one of these scout ants finds a potential nest, she assesses the quality of the crevice based on a variety of factors including the size of the interior, the number of openings (based on light level), and the presence or absence of dead ants. The worker then returns to the destroyed nest, where she will wait for a short period before recruiting other workers to follow her to the nest she found using a process called tandem running. The waiting period is inversely related to the quality of the site; for instance, a worker that has found a poor site will wait longer than a worker that encountered a good site. As the new recruits visit the potential nest site and make their own assessment of its quality, the number of ants visiting the crevice increases. During this stage ants may be visiting many different potential nests. However, because of the differences in the waiting period the number of ants in the best nest will tend to increase at the greatest rate. Eventually, the ants in this nest will sense that the rate at which they encounter other ants has exceeded a particular threshold, indicating that the quorum number has been reached. Once the ants sense a quorum, they return to the destroyed nest and begin rapidly carrying the brood, queen, and fellow workers to the new nest. Scouts that are still tandem-running to other potential sites are also recruited to the new nest and the entire colony moves. Thus although no single worker may have visited and compared all of the available options, quorum sensing enables the colony as a whole to quickly make good decisions about where to move.

Quorum Sensing – Wikipedia

Embarrassingly Parallel

In the jargon of parallel computing, an embarrassingly parallel workload or embarrassingly parallel problem is one for which no particular effort is needed to segment the problem into a very large number of parallel tasks, and there is no essential dependency or communication between those parallel tasks.

A very common usage of an embarrassingly parallel problem lies within graphics processing units (GPUs) for things like 3D projection since each pixel on the screen can be rendered independently from any other pixel.

Embarrassingly parallel problems are ideally suited to distributed computing over the Internet (e.g. SETI@home), and are also easy to perform on server farms which do not have any of the special infrastructure used in a true supercomputer cluster.

Embarrassingly parallel – Wikipedia, the free encyclopedia