Planner.js

(function (factory) {
    if (typeof module === "object" && typeof module.exports === "object") {
        var v = factory(require, exports);
        if (v !== undefined) module.exports = v;
    }
    else if (typeof define === "function" && define.amd) {
        define(["require", "exports", "./World", "./Graph", "./Interpreter", "./Heuristics"], factory);
    }
})(function (require, exports) {
    "use strict";
    exports.__esModule = true;
    var World_1 = require("./World");
    var Graph_1 = require("./Graph");
    var Interpreter_1 = require("./Interpreter");
    var Heuristics_1 = require("./Heuristics");
    /********************************************************************************
    ** Planner
    
    The goal of the Planner module is to take the interpetation(s)
    produced by the Interpreter module and to plan a sequence of
    actions for the robot to put the world into a state compatible
    with the user's command, i.e. to achieve what the user wanted.
    
    You should implement the function 'makePlan'.
    The planner should use your A* search implementation to find a plan.
    ********************************************************************************/
    //////////////////////////////////////////////////////////////////////
    // exported functions, classes and interfaces/types
    /* Top-level driver for the Planner.
     * It calls `makePlan` for each given interpretation generated by the Interpreter.
     * You don't have to change this function.
     *
     * @param interpretations: List of possible interpretations.
     * @param currentState: The current state of the world.
     * @returns: List of planner results, which are the interpretation results augmented with plans.
     *           Each plan is represented by a list of strings.
     *           If there's planning error, it returns a string with a description of the error.
     */
    function plan(interpretations, currentState) {
        var errors = [];
        var plans = [];
        interpretations.forEach(function (result) {
            var theplan = makePlan(result.interpretation, currentState);
            if (typeof (theplan) === "string") {
                errors.push(theplan);
            }
            else {
                result.plan = theplan;
                if (result.plan.length == 0) {
                    result.plan.push("That is already true!");
                }
                plans.push(result);
            }
        });
        if (plans.length) {
            return plans;
        }
        else {
            // merge all errors into one
            return errors.join(" ; ");
        }
    }
    exports.plan = plan;
    /* The core planner function.
     * The code here is just a template; you should rewrite this function entirely.
     * In this template, the code produces a dummy plan which is not connected
     * to the argument 'interpretation'. Your version of the function should
     * analyse 'interpretation' in order to figure out what plan to return.
     *
     * @param interpretation: The logical interpretation of the user's desired goal.
     * @param state: The current world state.
     * @returns: A plan, represented by a list of strings.
     *           If there's a planning error, it returns a string with a description of the error.
     */
    function makePlan(interpretation, state) {
        // Create search graph, implements
        //      interface Graph<Node>
        //          outgoingEdges(node : Node) : Edge<Node>[];
        //          compareNodes : CompareFunction<Node>
        var planningGraph = new PlanningGraph(state);
        // Build anonymized functions
        //      goal : (n:Node) => boolean
        //      heuristics : (n:Node) => number
        var goal = function (node) {
            return goalTest(interpretation, planningGraph.state[node]);
        };
        var heuristic = function (node) {
            return Heuristics_1.heuristics(interpretation, planningGraph.state[node]);
        };
        // Perform A* search
        var searchResult = Graph_1.aStarSearch(planningGraph, 0, goal, heuristic, 20);
        console.log("Nodes visited: " + searchResult.visited.toString());
        if (searchResult.timeout == true) {
            return "search timed out";
        }
        var roughMoves = searchResult.path.map(function (i) { return planningGraph.action[i]; });
        var holding = !!state.holding;
        var arm = [state.arm[0], state.arm[1]];
        var plan = [];
        for (var _i = 0, roughMoves_1 = roughMoves; _i < roughMoves_1.length; _i++) {
            var stack = roughMoves_1[_i];
            if (stack[0] < 0)
                continue;
            if (arm[0] < stack[0]) {
                var diff = stack[0] - arm[0];
                if (diff == 1)
                    plan.push("Moving forward one row.");
                else
                    plan.push("Moving forward " + diff + " rows.");
            }
            while (arm[0] < stack[0]) {
                arm[0]++;
                plan.push('f');
            }
            if (arm[0] > stack[0]) {
                var diff = -(stack[0] - arm[0]);
                if (diff == 1)
                    plan.push("Moving backward one row.");
                else
                    plan.push("Moving backward " + diff + " rows.");
            }
            while (arm[0] > stack[0]) {
                arm[0]--;
                plan.push('b');
            }
            if (arm[1] < stack[1]) {
                var diff = stack[1] - arm[1];
                if (diff == 1)
                    plan.push("Moving right one column.");
                else
                    plan.push("Moving right " + diff + " columns.");
            }
            while (arm[1] < stack[1]) {
                arm[1]++;
                plan.push('r');
            }
            if (arm[1] > stack[1]) {
                var diff = -(stack[1] - arm[1]);
                if (diff == 1)
                    plan.push("Moving left one column.");
                else
                    plan.push("Moving left " + diff + " columns.");
            }
            while (arm[1] > stack[1]) {
                arm[1]--;
                plan.push('l');
            }
            var object_name = state.objects[stack[2]].toStringAdv();
            var number_of_object = World_1.world_object_counter(state.objects[stack[2]], state);
            var identifier = (number_of_object == 1) ? 'the' : 'a';
            plan.push(holding ? "Dropping the " + object_name : "Picking up " + identifier + " " + object_name);
            plan.push(holding ? 'd' : 'p');
            holding = !holding;
        }
        if (arm[0] != 0 || arm[1] != 0)
            plan.push('Going back to starting position.');
        while (arm[0] > 0) {
            arm[0]--;
            plan.push('b');
        }
        while (arm[1] > 0) {
            arm[1]--;
            plan.push('l');
        }
        // Translate result into moves
        return plan;
    }
    var PlanningGraph = (function () {
        function PlanningGraph(initialState) {
            this.action = [[-1, -1, '#0 ']];
            this.state = [initialState];
        }
        PlanningGraph.prototype.compareNodes = function (a, b) {
            return a - b;
        };
        PlanningGraph.prototype.outgoingEdges = function (node) {
            var result = [];
            var object_id;
            for (var row = 0; row < this.state[node].stacks.length; row++) {
                for (var col = 0; col < this.state[node].stacks[row].length; col++) {
                    // Don't include "undo"
                    if (row == this.action[node][0])
                        if (col == this.action[node][1])
                            continue;
                    // Check for validity and generate next state
                    var nextState = this.tryMove(this.state[node], row, col);
                    if (nextState == undefined)
                        continue;
                    // for talking arm
                    if (nextState.holding) {
                        object_id = nextState.holding;
                    }
                    else {
                        var height = nextState.stacks[row][col].length;
                        object_id = nextState.stacks[row][col][height - 1];
                    }
                    // Add to result
                    var edge = new Graph_1.Edge();
                    edge.from = node;
                    edge.to = this.action.length;
                    edge.cost = 1;
                    if (!nextState.holding) {
                        edge.cost += Math.abs(row - this.action[node][0]);
                        edge.cost += Math.abs(col - this.action[node][1]);
                    }
                    result.push(edge);
                    // Add to graph
                    this.action.push([row, col, object_id]);
                    this.state.push(nextState);
                }
            }
            // Don't need to retain expanded states
            this.state[node] = null;
            return result;
        };
        PlanningGraph.prototype.tryMove = function (state, row, col) {
            // number of objects in affected stack
            var height = state.stacks[row][col].length;
            // deep (enough) copy
            var newStacks = [];
            var k = state.stacks.length;
            while (k--)
                newStacks[k] = state.stacks[k];
            k = state.stacks[row].length;
            newStacks[row] = [];
            while (k--)
                newStacks[row][k] = state.stacks[row][k];
            if (state.holding == null) {
                if (height > 0) {
                    newStacks[row][col] = [];
                    while (height--)
                        newStacks[row][col][height] = state.stacks[row][col][height];
                    var holding = newStacks[row][col].pop();
                    return {
                        "stacks": newStacks,
                        "holding": holding,
                        "arm": [0, 0],
                        "objects": state.objects,
                        "examples": null
                    };
                }
                else {
                    // Nothing to pick up
                    return null;
                }
            }
            else {
                if (height == 0) {
                    newStacks[row][col] = [state.holding];
                    return {
                        "stacks": newStacks,
                        "holding": null,
                        "arm": [0, 0],
                        "objects": state.objects,
                        "examples": null
                    };
                }
                else {
                    var obj1 = state.objects[state.holding];
                    var obj2 = state.objects[state.stacks[row][col][height - 1]];
                    if (Interpreter_1.physical_laws("ontop", obj1, obj2) || Interpreter_1.physical_laws("inside", obj1, obj2)) {
                        newStacks[row][col] = [];
                        while (height--)
                            newStacks[row][col][height] = state.stacks[row][col][height];
                        newStacks[row][col].push(state.holding);
                        return {
                            "stacks": newStacks,
                            "holding": null,
                            "arm": [0, 0],
                            "objects": state.objects,
                            "examples": null
                        };
                    }
                    else {
                        return null;
                    }
                }
            }
        };
        return PlanningGraph;
    }());
    function goalTest(interpretation, state) {
        // If any conjunction is true, return true
        var i = interpretation.conjuncts.length;
        while (i--) {
            var alltrue = interpretation.conjuncts[i].literals.every(function (lit) { return xor(!lit.polarity, Interpreter_1.current_relation(state, lit.relation, lit.args[0], lit.args[1])); });
            if (alltrue)
                return true;
        }
        return false;
    }
    function xor(a, b) {
        return a ? !b : b;
    }
});