As humans we are continually engaged in problem solving.  For example:

  • Planning a route between destinations
  • Writing a computer algorithm
  • Planning our weekly grocery shop

We have solved the problem of general problem solving but what is the algorithm? Is general problem solving a tractable problem that could be implemented as a computer program? Let's start with a classic problem and think about the process of solving it.

A fox, chicken and sack of grain

This is a classic brain teaser that is formulated in natural language as:

You have a fox, a chicken and a sack of grain. You must cross a river with only one of them at a time. If you leave the fox with the chicken he will eat it; if you leave the chicken with the grain he will eat it. How can you get all three across safely?

(Source: https://riddlesbrainteasers.com/fox-chicken-sack-grain/)

How do we solve this problem? We might observe that the only safe pairing is the fox and the grain.  That dictates our first move must be to transport the troublesome chicken.  Having separated the chicken we want to invert all the positions so we have two items (fox and grain) on the far shore and just one item (chicken) on the near shore.  Finally we can transport the chicken over and we're done.

Now, if we think a bit about the problem solving algorithm that our brains exercised to find the above solution, we can see that it had to do a few things:

  • Translate the natural language description into a world model:
    • Instantiate the nouns (e.g. fox, river, self)
    • Place the nouns in the world
      • For an initial state
      • For a successful outcome
  • Determine how the model can be manipulated:
    • Determine how the verbs translate into model changes
    • Determine the rules governing the possible moves
  • Manipulate the model:
    • Find a sequence of moves from starting state to desired outcome

Could we implement something like this in a computer program? It sounds simple if you say it fast enough but we're glossing over a few complexities.

Common knowledge

The first issue is the omission of common knowledge from the problem description.  For example, consider the question posed at the end of the problem:

How can you get all three across safely?

What does this mean? Obviously we know it means without any of them being eaten but this isn't stated explicitly - to define the target outcome we depend on the common knowledge that if you were eaten, you weren't safe or at least that you don't exist anymore.

We also need to know how all the verbs translate to the model. What does it mean in model space to 'cross' something or to 'eat' something?

Multiple description possibilities

There are numerous ways to describe this same problem using natural language. For instance, we could have said:

You're standing by a river with a fox, a chicken and a sack of grain. You must cross but can only take one of them at a time. Foxes eat chickens and chickens eat grain. How can you transport all three to the other side without incident?

Multiple model possibilities

What should our world model look like? How simple can we make our model while retaining enough degrees of freedom to solve a general problem?

Does it need to represent objects in 3D space or can we just model entities and relationships as logical sets and forget about space altogether?

Where to start?

There are quite a few problems to solve here and we're only considering an easy problem at the moment. Nevertheless, we have to start somewhere.

We can make life easier by formalising the problem description and ensuring all the relevant information is present. We can come back later to the problem of translating the natural language problem into a formal language and handling missing information.

Let's also start with a simple model based on relationships and eschew the complexity of spacial dimensions.  Can we make such a model work for this simple problem?

Next time

We'll build a model and run it with a formal description of the problem to see if we can achieve any success.