AI_Kit

AI_Kit aims to be a single dependency for various classic AI algorithms.

Core project goals are:

• convenient and ergonomic interfaces to various algorithms by building around traits.
• only build what you need through the use of feature flags
• performance
• easy to understand implementations

All of the algorithms (documented below) operate on several core traits, BindingsValue, Unify, Operation.

ai_kit provides optional data structures that implement these traits, allowing all algorithms to be usable out of the box - see Datum and Rule. Quick examples are provided before, followed by more in-depth documentation.

Installation

You can use this library by adding the following lines to your Cargo.toml file:

[dependencies]
ai_kit = "0.1.0"

and adding extern crate ai_kit to your crate root.

Documentation

This README provides an introduction.

API Documentation is available here

Core Concepts

There are three traits and one structure to understand when using this library:

Bindings - similar to a key/value lookup, but with utilities for ensuring that two (or more) keys have the same value.

BindingsValue - a trait allowing a data structure to be used by the Bindings data structure.

Unify - a trait for data structure can be unified with another of the same type.

Operation - a trait for mapping some number of Unify instances to some number of other Unifys. This is used for implementing Forward and Backward inferencing.

Unify

Two data structures can be unified if all of their components are the same or at least of the fields that differ is a variable. The Datum structure implements Unify. Here is an example of unifying datums.

Bindings

When successful, the unification process returns a Bindings structure, which maps variable names to their values (when known). It also allows for specifying that two variables are equivalent; in that case, when the value for one variable is found, it is considerd the value for another.

Anything that implements ai_kit::core::BindingsValue can be used with Bindings; Datum implements BindingsValue:

// Example of using the ai_kit::datum::Datum for variable bindings.

extern crate ai_kit;

use ai_kit::core::Bindings;
use ai_kit::datum::Datum;

fn main() {
    // Create empty bindings
    let bindings : Bindings<Datum> = Bindings::new();

    // Set the variables "?x" and "?y" equal to each other
    let bindings = bindings
        .set_binding(&"?x".to_string(), Datum::Variable("?y".to_string()));

    // Set the value of "?x"
    let bindings = bindings.set_binding(&"?x".to_string(), Datum::Float(1.0));

    // Verify that "?y" now has the same value
    
    assert_eq!(bindings.get_binding(&"?x".to_string()), Some(Datum::Float(1.0)));
}

Operation

There are times when a program has certain facts from which further facts can be inferred. This is implemented by the Operation trait. This is used to implement forward inference and planning. An example of forward chaining reasoning (also called Modus Ponens), would the following:

All men are mortal.
Socrates is a man.
Therefore Socrates is mortal.

The Rule struct implements Operation, and we use it to perform the above inference in rust.

Algorithms

Constraints

Feature with-constraint

A simple and limited library for checking and satisfying constraints.

Forward Inference

Feature with-forward-inference

Implementation of forward-chaining inference - essentially this is inference via Modus Ponens.

Example.

Planning

Feature with-planner

Planning with backtracking.

Example

Pedigree

Misc data-structures and code for representing the path taken to derive a given inference.

Default Trait Implementations

The above algorithms operate on any structures that implement the appropriate core traits (BindingsValue, Unify and Operation).

ai_kit provides default structures that implement the core traits which should be sufficient for many use-cases.

Datum

Feature with-datum.

The datum::Datum structure implements the BindingsValue and Unify traits.

	#[derive(Clone, Debug, Serialize, Deserialize, PartialOrd)]
	pub enum Datum {
	    Nil,
	    String(String),
	    Int(i64),
	    Float(f64),
	    Variable(String),
	    Vector(Vec<Datum>),
	}

Datum Implements Unify

Because Datum implements the Unify trait, Datum can be unified.

extern crate ai_kit;

use ai_kit::core::{Bindings, Unify};
use ai_kit::datum::Datum;

fn main() {
    let d = Datum::Float(0.0);
    let empty_bindings : Bindings<Datum> = Bindings::new();

    // These datums are the same, so they can be unified
    let bindings = d.unify(&Datum::Float(0.0), &empty_bindings);
    assert!(bindings.is_some());

    // These datums are not the same, so they cannot be unified
    let bindings = d.unify(&Datum::Float(1.0), &empty_bindings);
    assert!(bindings.is_none());
    
    // These datums differ, but the second is a variable, so they can be unified
    let bindings = d.unify(&Datum::Variable("?x".to_string()), &empty_bindings);
    assert!(bindings.is_some());

    // The bindings returned by unification so that the variable ?x now has the same value as d!
    assert_eq!(bindings.unwrap().get_binding(&"?x".to_string()), Some(d));
}

Rule

Feature with-rule.

The rule::Rule structure implements the Operation trait.

	#[derive(Clone, Debug, Deserialize, PartialEq, Serialize)]
	pub struct Rule<T: ConstraintValue, U: Unify<T>> {
	    pub constraints: Vec<Constraint>,
	    pub lhs: Vec<U>,
	    pub rhs: U,
	    _marker: PhantomData<T>,
	}

Rule Implements Operation

extern crate ai_kit;

use ai_kit::datum::Datum;
use ai_kit::infer::InferenceEngine;
use ai_kit::rule::Rule;
use std::marker::PhantomData;

fn main() {
    // Encode knowledge about mortality
    let rules = vec![
        (
            "rule_of_mortality".to_string(),    // Rules need ids for inferencing
            Rule {
                constraints: Vec::new(),
                lhs: vec![
                    Datum::Vector(
                        vec![
                            Datum::Variable("?x".to_string()),
                            Datum::String("isa".to_string()),
                            Datum::String("human".to_string()),
                        ]
                    )
                ],
                rhs: Datum::Vector(vec![
                    Datum::Variable("?x".to_string()),
                    Datum::String("isa".to_string()),
                    Datum::String("mortal".to_string()),
                ]),
                _marker: PhantomData,
            }
        ),
    ];
    
    // Setup our initial knowledge about socrates
    let facts = vec![
        (
            "socrates_is_hu``man".to_string(),      // Facts need ids for inferencing
            Datum::Vector(
                vec![
                    Datum::String("socrates".to_string()),
                    Datum::String("isa".to_string()),
                    Datum::String("human".to_string()),
                ]
            )
        ),
    ];

    // Infer new knowledge!
    let mut inf_engine = InferenceEngine::new(
        "demo".to_string(),
        rules.iter().map(|&(ref id, ref f)| (id, f)).collect(),
        facts.iter().map(|&(ref id, ref r)| (id, r)).collect());
    let inferences = inf_engine.chain_forward();
    assert_eq!(inferences.len(), 1);
}

Planning Examples

Sudoku Solver

Forthcoming

N-Queens Solver

Forthcoming

NLP Parser

This example takes a bunch of words, and rules for aggregating words into phrases and sentences, and constructs a valid parse of the words. It then saves a graph in GraphViz .dot notation of the actual goal tree constructed into a "parse.dot" in the current working directory.

extern crate ai_kit;
#[macro_use]
extern crate serde_json;

use ai_kit::core::Bindings;
use ai_kit::datum::Datum;
use ai_kit::planner::*;
use ai_kit::rule::Rule;
use std::fs::File;
use std::io::Write;
use std::path;

macro_rules! from_json {
    ($type: ty, $json: tt) => ({
        use serde_json;
        let x: $type = serde_json::from_value(json!($json)).expect("Expected json decoding");
        x
    })
}

#[allow(unused)]
fn main() {
    /*
     * Inference rules that encode the parts of speech for each word and how to
     * compose parts of speech into sentences.
     */
    let rules: Vec<Rule<Datum, Datum>> = from_json!(Vec<Rule<Datum, Datum>>, [
          // Parts of speech for each word
          {"lhs": [{"str": "a"}], "rhs": {"str": "det"}},
          {"lhs": [{"str": "the"}], "rhs": {"str": "det"}},
          {"lhs": [{"str": "chased"}], "rhs": {"str": "verb"}},
          {"lhs": [{"str": "chased"}], "rhs": {"str": "verb"}},
          {"lhs": [{"str": "dog"}], "rhs": {"str": "noun"}},
          {"lhs": [{"str": "cat"}], "rhs": {"str": "noun"}},
          // Building phrases into sentences
          {"lhs": [{"str": "det"}, {"str": "noun"}], "rhs": {"str": "np"}},
          {"lhs": [{"str": "verb"}, {"str": "np"}], "rhs": {"str": "vp"}},
          {"lhs": [{"str": "np"}, {"str": "vp"}], "rhs": {"str": "sen"}}
        ]);

    // Our input data - a series of words
    let data: Vec<Datum> = from_json!(Vec<Datum>, [
          {"str": "a"},
          {"str": "the"},
          {"str": "dog"},
          {"str": "cat"},
          {"str": "chased"}
        ]);

    // Specify that our goal is to construct a sentence from the provided data using the provided rules
    let mut planner = Planner::new(&Goal::with_pattern(from_json!(Datum, {"str": "sen"})),
                                   &Bindings::new(),
                                   &PlanningConfig {
                                       max_depth: 5,
                                       max_increments: 50,
                                       // Don't reuse a given piece of data (ie, a word)
                                       reuse_data: false,
                                   },
                                   data.iter().collect(),
                                   rules.iter().collect());

    // Construct the first interpretation
    let result = planner.next();
    assert_eq!(result.is_some(), true);
    let (final_goal, bindings) = result.unwrap();

    // What are our expected leaves of the goal (ie, the order of parsed sentences)
    let expected_leaves: Vec<Datum> = vec![
    	"a".to_string(),
    	"dog".to_string(),
    	"chased".to_string(),
    	"the".to_string(),
    	"cat".to_string()
    ]
        .into_iter()
        .map(|s| Datum::String(s))
        .collect();

    // Verify that the leaves of our plan are as expected
    assert_eq!(final_goal.gather_leaves(&bindings), expected_leaves);

    // Render the plan using graphviz notation
    let graphviz_rendering : String = final_goal.render_as_graphviz();

    // Save the plan in the current working directory
    File::create(path::Path::new(&"parse.dot"))
        .and_then(|mut file| file.write_all(graphviz_rendering.as_str().as_bytes()));
}

Here is the expected content of "parse.dot":

graph "goal tree 'sen'" {

"'sen' [Actor(8)]" -- "'np' [Actor(6)]";
"'np' [Actor(6)]" -- "'det' [Actor(0)]";
"'det' [Actor(0)]" -- "'a' [Datum(0)]";

"'np' [Actor(6)]" -- "'noun' [Actor(4)]";
"'noun' [Actor(4)]" -- "'dog' [Datum(2)]";

"'sen' [Actor(8)]" -- "'vp' [Actor(7)]";
"'vp' [Actor(7)]" -- "'verb' [Actor(2)]";
"'verb' [Actor(2)]" -- "'chased' [Datum(4)]";

"'vp' [Actor(7)]" -- "'np' [Actor(6)]";
"'np' [Actor(6)]" -- "'det' [Actor(1)]";
"'det' [Actor(1)]" -- "'the' [Datum(1)]";

"'np' [Actor(6)]" -- "'noun' [Actor(5)]";
"'noun' [Actor(5)]" -- "'cat' [Datum(3)]";

}

If you have graphviz installed locally, you can convert this graph into a PNG file:

dot -Tpng parse.dot > parse.png

Feature Matrix

Some features depend on other features. This is summarized in the following table:

Skeptic Testing

Examples in this document are tested as part of the build process using skeptic.