Humans exceed capabilities of known AI algorithms on the Travelling Salesperson Problem?

Apparently so, says a friend, who notes,

The TSP is a pedagogical problem used to test new AI algorithms. It is used because it is in a class of problems where the complexity scales exponentially with problem size, making finding solutions using a computer very difficult.


Interestingly, human performance on the TSP scales linearly or near linearly with problem size. Either there is some shortcut humans are using, or they have some other capability not exhibited by AI algorithms.

Here’s more on the problem:

The Traveling Salesman Problem is one of the most intensively studied problems in computational mathematics. These pages are devoted to the history, applications, and current research of this challenge of finding the shortest route visiting each member of a collection of locations and returning to your starting point.

But bees can solve it.

What I would like to know is this: If the computer programmer became a travelling salesperson, would he solve an equivalent problem faster than the machine he is trying to use?

Abstract

Little research has been carried out on human performance in optimization problems, such as the Traveling Salesman problem (TSP). Studies by Polivanova (1974, Voprosy Psikhologii, 4, 41–51) and by MacGregor and Ormerod (1996, Perception & Psychophysics, 58, 527–539) suggest that: (1) the complexity of solutions to visually presented TSPs depends on the number of points on the convex hull; and (2) the perception of optimal structure is an innate tendency of the visual system, not subject to individual differences. Results are reported from two experiments. In the first, measures of the total length and completion speed of pathways, and a measure of path uncertainty were compared with optimal solutions produced by an elastic net algorithm and by several heuristic methods. Performance was also compared under instructions to draw the shortest or the most attractive pathway. In the second, various measures of performance were compared with scores on Raven's advanced progressive matrices (APM). The number of points on the convex hull did not determine the relative optimality of solutions, although both this factor and the total number of points influenced solution speed and path uncertainty. Subjects' solutions showed appreciable individual differences, which had a strong correlation with APM scores. The relation between perceptual organization and the process of solving visually presented TSPs is briefly discussed, as is the potential of optimization for providing a conceptual framework for the study of intelligence.
Received: 28 December 1998?/?Accepted: 20 January 2000

Computers: Most engineers must have guessed that they are not robots

A friend writes to say that nonsensical materialism is now being marketed to engineers, via IEEE, the largest professional engineering society in the world, with over 365 000 members.

This article, "I, Rodney Brooks, am a robot", appeared in the IEEE Spectrum which is the magazine that goes to all members:

I am a machine. So are you.

Of all the hypotheses I’ve held during my 30-year career, this one in particular has been central to my research in robotics and artificial intelligence. I, you, our family, friends, and dogs—we all are machines. We are really sophisticated machines made up of billions and billions of biomolecules that interact according to well-defined, though not completely known, rules deriving from physics and chemistry. The biomolecular interactions taking place inside our heads give rise to our intellect, our feelings, our sense of self.

Accepting this hypothesis opens up a remarkable possibility. If we really are machines and if—this is a big if—we learn the rules governing our brains, then in principle there’s no reason why we shouldn’t be able to replicate those rules in, say, silicon and steel. I believe our creation would exhibit genuine human-level intelligence, emotions, and even consciousness.

This is beyond ridiculous.

There is no single, simple set of rules that governs the operations of the human brain or the mind that inhabits it.

It would make as much sense to say, "I am a tree" as "I am a robot." In some ways, more. Trees are life forms, like humans. There are at least some qualities that we share with trees (we need water, nutrients, and oxygen, and we grow, reproduce and die, for example).

But despite all that, we are not trees. And we certainly are not robots. The fact that we can say "I am" anything at all, or "I am not" that thing certainly apprises us that we are not trees or robots. Philosophers call it the "hard problem" of consciousness, the sense of self.

As Mario and I pointed out in The Spiritual Brain, the "computer" theory of how the human mind works is badly in need of an early retirement.

Note: I don't know where the sign is from, but am told it is somewhere in Britain.

Artificial intelligence: A look at things that neither we nor computers can discover

Recently (April 15, 2008), Robert J. Marks II, Distinguished Professor of Electrical & Computer Engineering at Baylor University in Texas, addressed a joint meeting of the local American Scientific Affiliation and the Baylor Society for Conversations in Religion, Ethics and Science, on the limitations of computer models of life and mind:

Computing has no theory of everything (T.O.E.). We're uncertain whether physics has a T.O.E. as revealed in M-theory but, due to the genius of Kurt Godel 75 years ago, smart people like Stephen Hawking are starting to doubt it.

This is because of a new startling mathematical idea from algorithmic information theory (AIT): There exist things that are true that cannot be derived from fundamental principles. Some things are true simply because they are true.

Many claim God cannot be proved. (Although I'll show you Godel's short mathematical proof of God's existence). There are some things we know exist that we can prove we will never know.

Most doubt a computer program will ever write a deeply meaningful poem or a classic novel. How about something simpler? Can we look at an arbitrary computer program and decide whether or not it will ever print out the number 3?

We can for some programs. But Alan Turing, the founder of computer science, proved it is impossible to write a program to analyze another arbitrary program to tell us whether or not a 3 will be printed.

In fact, we can't write a computer program to determine anything another arbitrary computer program will do. (This is called Rice's theorem.) To find out, we need to run the program.

We can also prove there are numbers of finite precision numbers a computer can't compute. One of these is Chaitin's number, an astonishing constant between zero and one we know exists.

If we knew Chaitin's constant to finite precision - one single number - we could solve many open problems in mathematics. These include the Riemann hypothesis, Goldbach's conjecture and whether or not there is an odd perfect number.

Chaitin's constant exists, but we can prove we will never know it. These and other mind bending properties in the field of AIT [artificial intelligence theory] seem too far fetched to be true, but with a minimum of math, I will convince you otherwise.

Sounds interesting. I have written to ask him how it turned out.

By the way here are some other Mindful Hack stories on how the human brain differs from a computer:

Mind vs. meat vs. computers - the differences

Let the machine read your mind (We offer an installment plan!)

Free will: In fruit flies yet?

Emotion machines - so that's what we are! (?)

Mind-computer blend: Who believes in this?

Artificial intelligence: Making the whole universe intelligent?

Brain cells release information more widely than previously thought.