Team:Alberta/Background

Background

The Travelling Salesman Problem

MapMen is Team Alberta's endeavour to create a biological computer capable of solving Travelling Salesman Problems (TSP), a general form of problem that asks:

Given a set of cities, and a list of the distances between each pair of those cities, what is the shortest possible route that travels to every city exactly once and then returns to the origin city?

Real-World Issues

The TSP is named after the concept of a hypothetical salesman who is planning a route to visit his customers in various neighbouring towns, but wants to maximize profits by using the shortest route — a helpful example to illustrate the usefulness of the problem: businesses around the world employ TSP-solving or related problem-solving software to help optimize their travelling needs, including in particular large courier companies that need to delivery millions of packages daily, and must reduce the expense of delivery vehicles and cut down travel time in any way possible, but also airliners, postal services, consumer GPS route-planning software, video-game pathfinding AI, and even electronics manufacture, in which a robot soldering arm must have an efficient path through the solder points to ensure maximum production over time.

The Computational Wall

The TSP is not only practically valuable, but also mathematically significant, because it belongs to a class of problems that are considered computationally difficult. The key difficulty with the TSP is due to the fact that it is an optimization problem: while for practical purposes any decent, short route is acceptable, a given TSP is nevertheless only considered "solved" when one verifies that one has obtained the shortest possible route. Mathematical verification of this sort requires what is called a "brute force" approach, in which one explores each and every possible route, tallying the total distance of each one, and then compares them all directly to guarantee the optimal route has been identified. As one increases the number of cities that must be included in the route, the time required for the brute-force approach becomes impossibly large.

Why Biocomputing?

Through synthetic biology, the creation of biological computers has opened a new avenue of possibility for solving TSPs more rapidly: using DNA molecules and bacterial cells as processors, one can compute billions of routes simultaneously, drastically reducing the time required through this massively parallel approach. By employing far more processors than there are routes through a given network, the processing time can be reduced to a standstill. A biological computer is also unique because it can solve problems stochastically: while every possible route is explored by the computer, preferable routes (short ones) will predominate among the generated products, allowing identification of the optimal route by population, rather than by a slower, deterministic approach.

A Long Road

A number of previous attempts have been made to produce biocomputer solutions to the TSP, often involving pure DNA computing with no living organism present, including attempts by Leonard Adleman of RSA encryption fame, as well as previous efforts by the Davidson College/Missouri Western State University iGEM team, whose 2006 entry attempted to solve another challenging computational problem called the Burnt Pancake Problem, and in 2007 entered a DNA computing solution for the Hamiltonian Path Problem. Though related to the TSP, the Hamiltonian Path Problem attempts to discern if there is any possible route through a network, rather than picking the shortest possible one.

MapMen represents the latest in a line of attempts to refine the biological approach and create ever- increasingly powerful biological computers – and is the first of its kind to employ living cells to solve a travelling salesman problem.