Graph Traversal

Graph Traversal Example:

Below is an example of a small instance of how the graph traversal will interact with the user (as currently visualized), as well as how edge weights will be updated to facilitate learning.

Example graph state where we’ve initially determined that the user drives a sedan and the symptom is that it wont start.  Our traversal begins at the “Won’t Start” node.

At each step of the traversal we define and display the probabilities of each leaf node that exists down the tree as the product of the edge weights in the shortest path to the leaf. As we are at the “Won’t Start” node, the probabilities would be for example:

Out of Gas: 36%

Spark Plugs Are Bad: 24%

Battery is Dead: 32%

Starter Motor is Bad: 8%

These values are updated at each step of traversal to give the user an updating list of probable problems.

Traversal:

We do a greedy graph search using the edge weights defined by the probabilities p. We reach the “Turn over?” mode at which point the traversal needs user input. The probabilities associated with the edges out from this node are built from past traversals, i.e. what users have expressed in the past. The application will ask the user for input at this node, specifically asking if the engine turns over when the key is turned. Lets assume that the user responds that it does indeed turn over. We then proceed to the transition state, a state that does not require user input and will proceed to the next state based on edge weights. In this simplified example we then reach the answer state “Out of Gas”.

At this point we have an answer for the user, their car may be out of gas. We would inform the user that this is probably the problem and perhaps provide a link to a video showing how to add gas to their vehicle. At this point, we will wait again for user input. Specifically we want the user to tell us if this was the problem. For this example let’s assume that the car was not out of gas, and we haven’t fixed the problem. The user informs the application of this, and traversal continues by going back to the transition state and proceeding to the next leaf node--the answer state “Spark Plugs Are Bad”.

We again recommend a DIY process or a mechanic to fix the problem and prompt the user for feedback. Let us assume that this did indeed fix the user’s vehicle. At this point we trace back the path and update the probabilities of each transition to reflect the new data.

This new graph structure represents a better informed graph and will be used for the future sedan queries and all graphs inheriting from the sedan graph.