GraphPlanAlgorithm.java

package aima.core.logic.planning;

import aima.core.logic.fol.kb.data.Literal;

import java.util.*;
import java.util.stream.Collectors;

/**
 * Artificial Intelligence A Modern Approach (3rd Edition): Figure 10.9 page
 * 383.<br>
 * <br>
 *
 * <pre>
 *
 * function GRAPHPLAN(problem) returns solution or failure
 *
 *  graph ← INITIAL-PLANNING-GRAPH(problem)
 *  goals ← CONJUNCTS(problem.GOAL)
 *  nogoods ← an empty hash table
 *  for tl = 0 to ∞ do
 *    if goals all non-mutex in St of graph then
 *      solution ← EXTRACT-SOLUTION(graph, goals, NUMLEVELS(graph), nogoods)
 *      if solution ≠ failure then return solution
 *    if graph and nogoods have both leveled off then return failure
 *    graph ← EXPAND-GRAPH(graph, problem)
 * </pre>
 * <p>
 * Figure 10.9 The GRAPHPLAN algorithm. GRAPHPLAN calls EXPAND-GRAPH to add a
 * level until either a solution is found by EXTRACT-SOLUTION, or no solution
 * is possible.
 *
 * @author samagra
 * @author Ruediger Lunde
 */
public class GraphPlanAlgorithm {

    /** Graph which was created in the last <code>graphPlan</code> call. */
    private Graph graph;

    public Graph getGraph() {
        return graph;
    }

    /**
     * function GRAPHPLAN(problem) returns solution or failure
     *
     * @param problem the planning problem for which the plan is to be created
     * @return a solution or null
     */
    public List<List<ActionSchema>> graphPlan(PlanningProblem problem) {
        // graph ← INITIAL-PLANNING-GRAPH(problem)
        graph = new Graph(problem);
        // goals ← CONJUNCTS(problem.GOAL)
        List<Literal> goals = problem.getGoal();
        // nogoods ← an empty hash table
        Hashtable<Integer, List<Literal>> nogoods = new Hashtable<>();
        Level<Literal, ActionSchema> state;
        // for tl = 0 to ∞ do
        for (int tl = 0; ; tl++) {
            // St
            state = graph.getLiteralLevel(tl);
            // if goals all non-mutex in St of graph then
            if (checkAllGoalsNonMutex(state, goals)) {
                // solution ← EXTRACT-SOLUTION(graph, goals, NUMLEVELS(graph), nogoods)
                List<List<ActionSchema>> solution = extractSolution(graph, goals, tl, nogoods);
                // if solution ≠ failure then return solution
                if (solution != null)
                    return solution;
            } else {
                // seems to be missing in the book - but needed to guarantee termination! (RLu)
                nogoods.put(tl, goals);
            }
            // if graph and nogoods have both leveled off then return failure
            if (graph.levelledOff() && leveledOff(nogoods))
                return null;
            // graph ← EXPAND-GRAPH(graph, problem)
            graph.expand(problem);
        }
    }

    /**
     * This method extracts a solution from the planning graph.
     * <p>
     * Artificial Intelligence A Modern Approach (3rd Edition): page 384.<br>
     * <p>
     * We can define EXTRACT -SOLUTION as a backward search problem, where
     * each state in the search contains a pointer to a level in the planning graph and a set of
     * unsatisfied goals. We define this search problem as follows:
     * • The initial state is the last level of the planning graph, S n , along with the set of goals
     * from the planning problem.
     * • The actions available in a state at level S i are to select any conflict-free subset of the
     * actions in A i−1 whose effects cover the goals in the state. The resulting state has level
     * S i−1 and has as its set of goals the preconditions for the selected set of actions. By
     * “conflict free,” we mean a set of actions such that no two of them are mutex and no two
     * of their preconditions are mutex.
     * • The goal is to reach a state at level S 0 such that all the goals are satisfied.
     * • The cost of each action is 1.
     *
     * Here a simple depth-first search is used.
     *
     * @param graph    The planning graph.
     * @param goals    Goals of the planning problem.
     * @param level    Index of the level to be analyzed (starting with last level in the graph).
     * @param nogoods  A hash table to store previously calculated results.
     * @return a solution if found else null
     */
    private List<List<ActionSchema>> extractSolution(Graph graph, List<Literal> goals, int level,
                                                     Hashtable<Integer, List<Literal>> nogoods) {
        if (level <= 0)
            return new ArrayList<>();
        if (nogoods.containsKey(level) && nogoods.get(level).contains(goals))
            return null;

        Level<Literal, ActionSchema> currLevel = graph.getLiteralLevel(level);
        List<List<ActionSchema>> setOfPossibleActions = new ArrayList<>();
        HashMap<ActionSchema, List<ActionSchema>> mutexLinks = currLevel.getPrevLevel().getMutexLinks();
        for (Literal literal : goals) {
            List<ActionSchema> possibleActionsPerLiteral = new ArrayList<>(currLevel.getLinkedPrevObjects(literal));
            setOfPossibleActions.add(possibleActionsPerLiteral);
        }
        List<List<ActionSchema>> allPossibleSubSets = generateCombinations(setOfPossibleActions);
        for (List<ActionSchema> possibleSet : allPossibleSubSets) {
            boolean validSet = true;
            for (int i = 0; i < possibleSet.size() && validSet; i++) {
                ActionSchema firstAction = possibleSet.get(i);
                for (int j = i + 1; j < possibleSet.size() &&  validSet; j++) {
                    ActionSchema secondAction = possibleSet.get(j);
                    if (mutexLinks.containsKey(firstAction) && mutexLinks.get(firstAction).contains(secondAction))
                        validSet = false;
                }
            }
            if (validSet) {
                List<Literal> newGoals = new ArrayList<>();
                for (ActionSchema action : possibleSet) {
                    for (Literal literal : action.getPrecondition())
                        if (!newGoals.contains(literal))
                            newGoals.add(literal);
                }
                newGoals.sort(Comparator.comparing(Literal::hashCode)); // defined order necessary for nogood test
                List<List<ActionSchema>> solution = extractSolution(graph, newGoals, level-1, nogoods);
                if (solution != null) {
                    solution.add(possibleSet);
                    return solution;
                }
            }
        }
        nogoods.put(level, goals);
        return null;
    }

    public List<ActionSchema> asFlatList(List<List<ActionSchema>> solution) {
        return solution.stream().flatMap(Collection::stream)
                .filter(actionSchema -> !ActionSchema.NO_OP.equals(actionSchema.getName()))
                .collect(Collectors.toList());
    }

    /**
     * This method is used to check if all goals are present in a particular state
     * and none of them has a mutex link.
     *
     * @param level The current level in which to check for the goals.
     * @param goals List of goals to be checked
     * @return Boolean representing if goals all non mutex in St
     */
    private boolean checkAllGoalsNonMutex(Level<Literal, ActionSchema> level, List<Literal> goals) {
        if (!level.getLevelObjects().containsAll(goals))
            return false;
        boolean mutexCheck = false;
        for (Literal literal : goals) {
            List<Literal> mutexOfGoal = level.getMutexLinks().get(literal);
            if (mutexOfGoal != null) {
                for (Object object : mutexOfGoal) {
                    if (goals.contains(object)) {
                        mutexCheck = true;
                        break;
                    }
                }
            }
        }
        return (!mutexCheck);
    }

    private boolean leveledOff(Hashtable<Integer, List<Literal>> nogoods) {
        int lastLevel = nogoods.size()-1;
        if (lastLevel < 1)
            return false;
        return nogoods.get(lastLevel).equals(nogoods.get(lastLevel-1));
    }

    public List<List<ActionSchema>> generateCombinations(List<List<ActionSchema>> actionLists) {
        List<List<ActionSchema>> result = new ArrayList<>();
        if (actionLists.size() == 1) {
            result.add(actionLists.get(0));
        } else if (actionLists.size() > 1) {
            result = combineTwoLists(actionLists.get(0), actionLists.get(1));
            if (actionLists.size() > 2) {
                for (int i = 2; i < actionLists.size(); i++)
                    result = combineExtraList(result, actionLists.get(i));
            }
        }
        // sorting by increasing number of actions might reduce execution costs of first found solution.
        result =  result.stream().sorted
                (Comparator.comparing(x -> x.stream().filter(y -> !ActionSchema.NO_OP.equals(y.getName())).count()))
                .collect(Collectors.toList());
        return result;
    }

    // Helper methods for combinations and permutations.
    public List<List<ActionSchema>> combineTwoLists(List<ActionSchema> firstList, List<ActionSchema> secondList) {
        List<List<ActionSchema>> result = new ArrayList<>();
        for (ActionSchema firstAction : firstList) {
            for (ActionSchema secondAction : secondList) {
                result.add(Arrays.asList(firstAction, secondAction));
            }
        }
        return result;
    }

    public List<List<ActionSchema>> combineExtraList(List<List<ActionSchema>> combinedList, List<ActionSchema> newList) {
        List<List<ActionSchema>> result = new ArrayList<>();
        for (List<ActionSchema> combined : combinedList) {
            for (ActionSchema action : newList) {
                List<ActionSchema> tempList = new ArrayList<>(combined);
                tempList.add(action);
                result.add(tempList);
            }
        }
        return result;
    }
}