Archive for the ‘Cool’ Category

Coincidence? I think not. Admissible heuristics in A* search and human cognitive biases

Friday, October 7th, 2016

I was always wondered whether anybody made this parallel before. I am sure that some people had made it, but I couldn’t find anything on the web, so I might as well as write it up.

Part 1: A* search (for non-technical people)

A* is a search algorithm used in artificial intelligence and robotics. It is a way to search for solutions to a problem. One can of course, find solutions by randomly trying out stuff (1) or by methodically trying out everything (2). What A* does is that it tries to use some knowledge about how close we are to a solution – this is called a heuristic. Basically, try to imagine that the heuristic is playing a hot-cold game: as you search, it tells you “freezing”, “cold”, “getting warmer”, “hot!”.

Now, of course, if you would genuinely know the exact distance to the solution, we don’t even need to search, just walk there directly. So the heuristic is normally just an approximation. We would assume that the closer the heuristic to reality, the better for the search, but it turns out that things are more bizarre than that. It is provable that the good heuristics are the ones that underestimate the distance to the solution, that is, they are optimistic (3). These kind of heuristics will tell you “warm”, when it is merely “cold”, and “hot!” when it is merely “warm”. Even a heuristic which always yells “hot!” (4) is still better (5) than one that approximates better, but from the pessimistic. Note that this is a formally provable result.

How do we create such heuristics? Most of the time what we do is take an original problem and (a) ignore some of the difficulties of the problem such as assume that there are no traffic jams (6) or (b) attribute superpowers to ourselves.

Part 2: Some cognitive biases

Ok, here I will need to rely mostly on our good friend Wikipedia. Basically, a cognitive bias is a human reasoning pattern which psychologists believe to be “irrational” or “illogical”. Here are some examples:

  • The planning fallacy, first proposed by Daniel Kahneman and Amos Tversky in 1979, is a phenomenon in which predictions about how much time will be needed to complete a future task display an optimism bias (underestimate the time needed).
  • The optimism bias (also known as unrealistic or comparative optimism) is a cognitive bias that causes a person to believe that they are less at risk of experiencing a negative event compared to others.
  • The illusion of control is the tendency for people to overestimate their ability to control events; for example, it occurs when someone feels a sense of control over outcomes that they demonstrably do not influence.
  • Illusory superiority is a cognitive bias whereby individuals overestimate their own qualities and abilities, relative to others. This is evident in a variety of areas including, performance on tasks or tests, and the possession of desirable characteristics or personality traits.


So, is this a coincidence or not? Well, it hinges on whether the human problem solving style is anything similar to A* search. We are certainly very bad in systematically searching for something, we are bad in backtracking, and everybody loves the hot-cold game.

(1) stochastic search
(2) uniform cost search, for instance
(3) admissible heuristics
(4) h(x) = 0
(5) what does “better” mean in this context is a bit more complicated. Let us say that if the heuristic is pessimistic, you will probably not find the best solution.
(6) Problem relaxation

Invest in Dittmer

Thursday, April 22nd, 2010

I was in Sillicon Valley for a day this summer, and boy oh boy, how the names changed. The company where I worked in 2001-2002 (CPlane) of course, is nowhere, and of course the company who almost bought us is also nowhere. Our major target customers are all bankrupt, and our company investor Sun, well,… was bankr… acqui…. merged. The AT&T Research labs, where I worked in 1998 and 1999, is long time history.

So what remained? Here are the most solid institutions of Sillicon Valley.

Dittmer’s Gourmet Meats & Wurst-Haus, Inc


The Milk Pail Market

Sic transit gloria mundi  — good thing we can always fall back on cheeses and sausages.

Walk score

Saturday, November 24th, 2007

Well, one of the interesting uses of Google Maps is the Walk Score website – from a typed in address it infers how walking friendly the neighborhood is. It seems that it looks up the closest restaurant, grocery store, bookstore and so on, and calculates the score based on whether I can walk there or not.

Without further ado: the score for our Orlando house is 12: which means: Driving Only: Virtually no neighborhood destinations within walking range. You can walk from your house to your car!

I would add to this that the score is somewhat optimistic, as it does not take into consideration whether the closest destination is acceptable – in my case, the closest “general purpose” bookstore is 3 miles away, well, good luck with that.

Future University of Hakodate

Monday, May 22nd, 2006

I have just came back from Japan, where the agent conference was organized at the location of the Future University of Hakodate (FUN), a recently established engineering school which had built a “futuristic” building, which is housing the _entire_ university (although their current degree offerings are basically what our SEECS is, with some industrial engineering thrown in the mix). Their building concept was based on the idea of openness: basically all the walls are glass, the graduate student offices are in the “open air”, meeting rooms are just demarcated areas in a wide open area, etc. I thought I will share with you some of the pictures I had taken. I am not hundred percent sure I like the idea, but it is intriguing.