Categories > Artificial Intelligent



A stupid Robot appears without Artificial Neural Network!

Posted on March 23rd, 2012 By Danial Javanmardi


Artificial Neural Network (ANN)?

The field of neural networks was pioneered by Bernard Widrow of Stanford University in the 1950s. Neural networks are currently used prominently in voice recognition systems, image recognition systems, industrial robotics, medical imaging, data mining and aerospace applications.

What Is A Artificial Neural Network?

“…a computing system made up of a number of simple, highly interconnected processing elements, which process information by their dynamic state response to external inputs.”
In “Neural Network Primer: Part I” by Maureen Caudill, AI Expert, Feb. 1989

The Basics of Artificial Neural Networks

Neural networks are typically organized in layers. Layers are made up of a number of interconnected ‘nodes’ which contain an ‘activation function’. Patterns are presented to the network via the ‘input layer’, which communicates to one or more ‘hidden layers’ where the actual processing is done via a system of weighted ‘connections’. The hidden layers then link to an ‘output layer’ where the answer is output.

Most ANNs contain some form of ‘learning rule’ which modifies the weights of the connections according to the input patterns that it is presented with. In a sense, ANNs learn by example as do their biological counterparts; a child learns to recognize dogs from examples of dogs.

How Do Neural Networks Differ From Conventional Computing?

In a serial system (and a standard parallel one as well) the computational steps are deterministic, sequential and logical, and the state of a given variable can be tracked from one operation to another. In comparison, ANNs are not sequential. There are many simple ones which generally do nothing more than take the weighted sum of their inputs from other processors. ANNs do not execute programmed instructions; they respond in parallel to the pattern of inputs presented to it. There are also no separate memory addresses for storing data. Instead, information is contained in the overall activation ‘state’ of the network. ‘Knowledge’ is thus represented by the network itself, which is quite literally more than the sum of its individual components.

What Are Their Advantages Over Conventional Techniques?

This applies to problems where the relationships may be quite dynamic or non-linear. ANNs provide an analytical alternative to conventional techniques which are often limited by strict assumptions of normality, linearity, variable independence etc. Because an ANN can capture many kinds of relationships it allows the user to quickly and relatively easily model phenomena which otherwise may have been very difficult or impossible to explain otherwise.

Case Study – 3D Interactive Map for National University of Singapore

Before goring further, I would like to point out that the problem arose in a path finding of a robotic simulation, you could look at the details of the project at  Link or download it directory from iTunes for iPad devices.

I implemented a recursive path finding algorithm. This recursive algorithm works based on a pre-set of nodes connected together. Each node has four pointers containing further direction: Top, bottom, Left and Right. The recursive algorithm simply walks through each node and looking for each of these four directions one by one toward reaching its final destination; an illustration, consider the following 7 nodes: A, B, C, D, E, F, G, H.

A (bottom->D, Right->B)
B (Right->C, Left->B)
C (Left->B)
D (bottom->G, Right->E, Top->A)
E (Right->F, Left->D)
F (Left->E)
G (Right->H, Top->D)
H (Left->G)

These nodes when comes to an overall view will display the following figure.


A—B—C
|
D—E—F
|
G—H

In this example, suppose the walker started node is Node A and wants to go to Node H as its final destination. Node A looks at its own Right, bottom, Left and Top by order; its right pointed to Node B as a result he chooses to go to Node B; Node B in same pattern chooses to go to its right, Node C. When the walker reaches node C; as its Right, Top and Bottom is blocked, Node C reverts back to Node B. As well node B reverts back Node A. The walker comes back to the start point again. Then Node A goes to its bottom node base on the order; which means it goes to Node D. Node D goes to its right Node E and then Node F. As Node F is blocked; it goes back to Node E and Node D. Afterwards, Node D chooses to go its bottom, Node G according to walker order. From there Node G goes to Node H. Finally, the walker reaches its final destination.

 

Pseudocode: Recursive Path Finding Algorithm

ArrayList findPath(GameObject currentPoint , GameObject targetPoint , ArrayList InputArrayList)
{

  1. Duplicate InputArrayList as tempArrayList
  2.  

  3. If the currentPoint equals to target Point return inputArrayList
    //*** End Condition found target
  4.  

  5. If the Right side of the currentPoint is empty goto step 4
  6. 3.1- Add currentPoint to tempArrayList
    //*** Call Right
    3.2- tempArrayList = findPath(currentpoint.Right, targetPoint, tempArrayList);
    3.3- If tempArrayList is not null return tempArrayList

  7. If the Bottom side of the currentPoint is empty goto step 5
  8. 4.1- Add currentPoint to tempArrayList
    //*** Call Bottom
    4.2- tempArrayList = findPath(currentpoint. Bottom , targetPoint, tempArrayList);
    4.3- If tempArrayList is not null return tempArrayList

  9. If the Left side of the currentPoint is empty goto step 6
  10. 5.1- Add currentPoint to tempArrayList
    //*** Call Left
    5.2- tempArrayList = findPath(currentpoint.Left, targetPoint, tempArrayList);
    5.3- If tempArrayList is not null return tempArrayList

  11. If the Top side of the currentPoint is empty goto step 7
  12. 6.1- Add currentPoint to tempArrayList
    //*** Call Top
    6.2- tempArrayList = findPath(currentpoint.Top, targetPoint, tempArrayList);
    6.3- If tempArrayList is not null return tempArrayList

  13. Return null;
    //*** End Condition does not found target

}

Note: The actual code is in C#, You can download it from this link.

Rise of problem in the case study:

As you understand this code; it has a weakness, to illustrate it; considering the following overall view of nodes, with the assumption that the start node is Node A and the final destination is Node H.


A—B—C
|
D—E—F—I
|         |    |
G—H—J—K

Though the best path solution is (A, D, G, H), The explained recursive path finding algorithm finds (A, D, E, F, I, K, J, H) as its solution; this really seems the Robot is a stupid robot :D !

The most important feature of Artificial Neural Network is the neuron’s ability to learn. This explained algorithm is a recursive algorithm; the robot behaves stupidly in some situations since it does not have the learning ability. Please consider the following two pictures. Figure 2 displays the result of implementing the learning ability for nodes while Figure 1 does not have this ability as a result in Figure 1 when the walker reaches path_4_6; it goes round de-tour to reach its final destination on path_2_5.


Figure 1: The recursive path finding algorithm




Figure 2: The recursive path finding algorithm with the ability to learn


Note: I would like to admit that there is another resolution apart from the ANN for the recursive path algorithm; which need to be revised the recursive algorithms to find all of the possible solutions and then choose the shortest path. As this is an actual real project based on the time limitation and as well as the target device is iPad without strong processor; I have chosen to resolve the issue just by giving the node learning ability.

To see the actual case study, please use the following two links, once the page is loaded you need to go to Ground View and press GOTO on #16 “Multimedia Viewing Stations”. The size of the Web Version is around 20MB, you need the Unity3D Web Player.

Link, Nodes without learning ability.
Link, Nodes with learning ability.

Partially UML Diagram of the case study:

Sequence Diagram of Goto the Single Land Mark Scenario:

Class Diagram of PathManager Class in C#:

Further Resources:

  1. Wikipedia, Artificial neural network

Next Article: