Public Member Functions
	Graphplan (PDDLObject problem)
boolean	isLevelOff ()
String	opToString (Op op)
void	preprocessing () throws InvalidExpException
Plan	solve ()
Static Public Member Functions
static Properties	getParserOptions ()
static void	main (String[] args)
static void	printPlan (Plan plan)
static void	printUsage ()
Public Attributes
long	a_tried = 0
long	noop_tried = 0
PDDLObject	problem
Private Member Functions
void	addNewNoOp (final Fact fact)
boolean	addNewOp (Action action, Substitution sigma) throws InvalidExpException
boolean	are_dependent (final Op op1, final Op op2)
boolean	areMutexFact (int i, int j, int k)
boolean	areMutexOps (final int i, final int j, final int k)
boolean	contains (final BitSet facts, final int k)
void	expand (final int k)
BitSet[]	expToBitSet (final Exp exp) throws InvalidExpException
Plan	extract (final BitSet goals, final int k)
BitSet	getResolvers (final int i, final int k)
void	initFacts ()
void	initGoals () throws InvalidExpException
void	initNogoodsTable ()
void	initOps () throws InvalidExpException
void	initOpsDependences ()
void	initPlanningGraph () throws InvalidExpException
void	instantiateFacts (final AtomicFormula skeleton, final List< Term > args, final Substitution sigma)
void	instantiateOps (final Action action, final List< Term > param, final Substitution sigma) throws InvalidExpException
boolean	isApplicable (final Op op, final int k)
boolean	isMutexFree (final BitSet facts, final int k)
void	printOpAt (int k)
void	printOpMutexAt (int k)
void	printOpsTable ()
void	printPropAt (int k)
void	printPropMutexAt (int k)
Plan	search (final BitSet goals, final BitSet ak, final int k, final BitSet mutex)
Fact	selectGoal (BitSet goals)
Op	selectResolver (final BitSet resolvers)
HashSet< Literal >	toLiteralSet (final Exp exp) throws InvalidExpException
Private Attributes
BitMatrix	dependences
ArrayList< BitSet >	facts_layers
ArrayList< BitMatrix >	facts_mutex
ArrayList< Fact >	facts_table
int	facts_table_size
long	g_time = 0
BitSet	goals
int	levelOff = -1
long	m_time = 0
HashMap< Integer, Set< BitSet > >	nogoods
int	ops_index
ArrayList< BitSet >	ops_layers
ArrayList< BitMatrix >	ops_mutex
ArrayList< Op >	ops_table = new ArrayList<Op>(1000)
int	ops_table_size
long	p_time = 0
ArrayList< BitMatrix >	resolvers
long	s_time = 0

Detailed Description

This class implements the graphplan planner as an example of the pddl4j library. Only strips and typing are accepted.

Author:: Damien Pellier

Version:: 1.0

Definition at line 73 of file Graphplan.java.

Constructor & Destructor Documentation

Graphplan.Graphplan ( PDDLObject problem ) [inline]

Creates a new java graphplan planner to solve a specific problem.

Parameters:

problem the problem to solve.

Definition at line 185 of file Graphplan.java.

Member Function Documentation

void Graphplan.addNewNoOp ( final Fact fact ) [inline, private]

Creates a new noop operator from a specific fact.

Parameters:

fact the fact.

Definition at line 913 of file Graphplan.java.

boolean Graphplan.addNewOp	(	Action	action,
		Substitution	sigma
	)		throws InvalidExpException `[inline, private]`

Add a new op created from a specific pddl action.

Parameters:

action	the action.
sigma	the mapping between the parameters and their values.

Returns:: true if a new op is added; false otherwise.

Exceptions:

InvalidExpException if the unexpected pddl expression occurs in the action definition.

Definition at line 890 of file Graphplan.java.

boolean Graphplan.are_dependent	(	final Op	op1,
		final Op	op2
	)		`[inline, private]`

Returns true if two operators are dependent, i.e, if an operator delete an precondition or an add effect of the other.

Parameters:

op1	The first operator.
op2	The second operator

Returns:: true if two operators are dependent, false otherwise.

Definition at line 964 of file Graphplan.java.

boolean Graphplan.areMutexFact	(	int	i,
		int	j,
		int	k
	)		`[inline, private]`

Returns true if two facts are mutex at a specified level. Two facts are mutex if at least one operator that produce the facts are mutex in the previoud level k - 1.

Parameters:

i	the first fact.
j	the second fact.
k	the level where the test must be done.

Returns:: true if two facts are mutex at a specified level; false otherwise.

Definition at line 670 of file Graphplan.java.

boolean Graphplan.areMutexOps	(	final int	i,
		final int	j,
		final int	k
	)		`[inline, private]`

Returns true if two operator are mutex at a specified level. Two operators are mutex if the operators are dependent or an operator has a mutex precondition at level k;

Parameters:

i	the first fact.
j	the second fact.
k	the level where the test must be done.

Returns:: true if two operator are mutex at a specified level; false otherwise.

Definition at line 701 of file Graphplan.java.

boolean Graphplan.contains	(	final BitSet	facts,
		final int	k
	)		`[inline, private]`

Returns true if a specified set of fact is contains in a specific level of the graph.

Parameters:

facts	the facts to be tested.
k	the level of the graph where the test is done.

Returns:: true if a specified set of fact is contains in a specific level of the graph; falseotherwise.

Definition at line 552 of file Graphplan.java.

void Graphplan.expand ( final int k ) [inline, private]

Expands the kth level planning graph.

Parameters:

k	the level to expand.

Definition at line 563 of file Graphplan.java.

BitSet [] Graphplan.expToBitSet ( final Exp exp ) throws InvalidExpException [inline, private]

Transforms a pddl expression into a bit set representation.

Parameters:

exp	the expression to transform.

Returns:: a array of bit set with a length of 2 such the first bit set represents the positive fact of the expression and second bit set that represents the negative fact of the expression.

Exceptions:

InvalidExpException if an sub expression of the specified expression is not valid.

Definition at line 1033 of file Graphplan.java.

Plan Graphplan.extract	(	final BitSet	goals,
		final int	k
	)		`[inline, private]`

Extract the solution plan from the planning graph.

Parameters:

goals	the goals to be extracted.
k	the level of the graph where the goal must be extracted.

Returns:: the solution plan extract at level k.

Definition at line 364 of file Graphplan.java.

static Properties Graphplan.getParserOptions ( ) [inline, static]

Returns the default options of the compiler.

Returns:: the default options.

Definition at line 276 of file Graphplan.java.

BitSet Graphplan.getResolvers	(	final int	i,
		final int	k
	)		`[inline, private]`

Returns the set of resolvers of a specific fact at a specified level of the graph.

Parameters:

i	the fact.
k	the level of the graph.

Returns:: the set of resolvers of the fact i at level k of the planning graph.

Definition at line 500 of file Graphplan.java.

void Graphplan.initFacts ( ) [inline, private]

Enumerates all the facts of the planning problem.

Definition at line 782 of file Graphplan.java.

void Graphplan.initGoals ( ) throws InvalidExpException [inline, private]

Init the goals of the problem, i.e., convertes the goal of the in a pddl format to inner format.

Exceptions:

InvalidExpException if an invalid pddl expression is found in the pddl goal description of the problem.

Definition at line 1001 of file Graphplan.java.

void Graphplan.initNogoodsTable ( ) [inline, private]

Init the no goods goals table used to store goals search failure.

Definition at line 775 of file Graphplan.java.

void Graphplan.initOps ( ) throws InvalidExpException [inline, private]

Enumerates all the operators of the planning problem.

Exceptions:

InvalidExpException if an expression of an operator of the problem is not an accepted pddl expression.

Definition at line 832 of file Graphplan.java.

void Graphplan.initOpsDependences ( ) [inline, private]

Computes the static dependence between the operators of the planning problem.

Definition at line 929 of file Graphplan.java.

void Graphplan.initPlanningGraph ( ) throws InvalidExpException [inline, private]

Init the planning graph, i.e., create the first fact level of the planning graph.

Exceptions:

InvalidExpException if an invalid pddl expression is found in the pddl initial state description of the problem.

Definition at line 978 of file Graphplan.java.

void Graphplan.instantiateFacts	(	final AtomicFormula	skeleton,
		final List< Term >	args,
		final Substitution	sigma
	)		`[inline, private]`

Instantiates all the fact from a specific atomic formula skeleton of the problem.

Parameters:

skeleton	the atomic formula skeleton to instantiate.
args	the list of arguments of the atomic formula skeleton not yet instantiated.
sigma	the map containing for each argument already instantiated its value.

Definition at line 806 of file Graphplan.java.

void Graphplan.instantiateOps	(	final Action	action,
		final List< Term >	param,
		final Substitution	sigma
	)		throws InvalidExpException `[inline, private]`

Instantiates all the operator from a specific action of the problem.

Parameters:

action	the atomic formula skeleton to instantiate.
param	the list of parameters of the action not yet instantiated.
sigma	the map containing for each parameter already instantiated its value.

Exceptions:

InvalidExpException if an invalid pddl expression is found in the action.

Definition at line 861 of file Graphplan.java.

boolean Graphplan.isApplicable	(	final Op	op,
		final int	k
	)		`[inline, private]`

Returns true if a operator is applicable to specified level of the planning graph. An operator is applicable to proposition level k of a graph if its preconditions are included and are mutex free in the proposition level k.

Parameters:

op	The operator to be tested.
k	the level of graph where the test is done.

Returns:: true if a operator is applicable to specified level of the planning graph; false otherwise.

Definition at line 515 of file Graphplan.java.

boolean Graphplan.isLevelOff ( ) [inline]

Returns true if the fixed point of the planning graph was reached.

Returns:: true if the fixed point of the planning graph was reached; false otherwise.

Definition at line 724 of file Graphplan.java.

boolean Graphplan.isMutexFree	(	final BitSet	facts,
		final int	k
	)		`[inline, private]`

Returns true if a set of facts is mutex free in a specified proposition level of the planning graph.

Parameters:

facts	the facts to be tested.
k	the level of the graph at which the test is done.

Returns:: true if a set of facts is mutex free in a specified proposition level of the planning graph, false otherwise.

Definition at line 531 of file Graphplan.java.

static void Graphplan.main ( String[] args ) [inline, static]

The main method the jgraphplan planner.

Parameters:

args	an array of string representing the path of the planning domain and the problem.

Definition at line 201 of file Graphplan.java.

String Graphplan.opToString ( Op op ) [inline]

Returns a string representation of a specified operator.

Parameters:

op	the operator to convert.

Returns:: the string representation of the specified operator.

See also:: java.lang.Object::toString()

Definition at line 1235 of file Graphplan.java.

void Graphplan.preprocessing ( ) throws InvalidExpException [inline]

Executes the preprocessing of the problem, i.e, instantiates the operators of the problem, conmputes the static dependence between operators, init the firts level of the planning graph and the goal.

Exceptions:

InvalidExpException if an pddl expression of the goal or in an action definition is not accepted by the planner

Definition at line 759 of file Graphplan.java.

void Graphplan.printOpAt ( int k ) [inline, private]

Prints a operators layer at a specified layer.

Parameters:

k	the k layer.

Definition at line 1184 of file Graphplan.java.

void Graphplan.printOpMutexAt ( int k ) [inline, private]

Prints a mutex operator layer at a specified layer.

Parameters:

k	the layer.

Definition at line 1197 of file Graphplan.java.

void Graphplan.printOpsTable ( ) [inline, private]

Print the ops table.

Definition at line 1159 of file Graphplan.java.

static void Graphplan.printPlan ( Plan plan ) [inline, static]

Print a specified plan.

Parameters:

plan	the plan to print.

Definition at line 1131 of file Graphplan.java.

void Graphplan.printPropAt ( int k ) [inline, private]

Prints a propositions layer at a specified layer.

Parameters:

k	the layer.

Definition at line 1171 of file Graphplan.java.

void Graphplan.printPropMutexAt ( int k ) [inline, private]

Print a mutex propositions layer at a specified layer.

Parameters:

k	the layer.

Definition at line 1215 of file Graphplan.java.

static void Graphplan.printUsage ( ) [inline, static]

Print the usage of the graphplan command.

Definition at line 294 of file Graphplan.java.

Plan Graphplan.search	(	final BitSet	goals,
		final BitSet	ak,
		final int	k,
		final BitSet	mutex
	)		`[inline, private]`

Search the actions that resolve a list of goals at a speific level.

Parameters:

goals	The list of goals to resolve.
ak	The set of actions that already solve the goals.
k	The level of the planning graphh where the search is done.
mutex	the set of mutex already computed.

Returns:: The plan that solve the list of goals or null if no plan can solve it.

Definition at line 395 of file Graphplan.java.

Fact Graphplan.selectGoal ( BitSet goals ) [inline, private]

Select a goal from a set of goals. The goals selection is based on the level heuristics, i.e., choose always the goal fact that appears earliest in the planning graph because it is easier to find a solution for it.

Parameters:

goals the set of goals from which a goal must be selected.

Returns:: the goal selected.

Definition at line 442 of file Graphplan.java.

Op Graphplan.selectResolver ( final BitSet resolvers ) [inline, private]

Select a resolver from a set of resolvers. The resolver selection is based on the level heuristics, i.e., choose always the resolver that appears latest in the planning graph. it.

Parameters:

resolvers the set of resolvers from which a resolver must be selected.

Returns:: the selected resolver according to the level based heuristics.

Definition at line 464 of file Graphplan.java.

Plan Graphplan.solve ( ) [inline]

Solves the planning problem and returns the first solution plan found.

Returns:: the first solution plan found or Plan.Failure if no solution was found.

Definition at line 309 of file Graphplan.java.

HashSet<Literal> Graphplan.toLiteralSet ( final Exp exp ) throws InvalidExpException [inline, private]

Converts a ground pddl expression into a set of literals.

Parameters:

exp	the expression that must be converted.

Returns:: a set of literal that represents the specified expression.

Exceptions:

InvalidExpException if an sub expression of the specified expression is not valid.

Definition at line 1069 of file Graphplan.java.

Member Data Documentation

long Graphplan.a_tried = 0

The number of actions tried for finding a solution plan.

Definition at line 173 of file Graphplan.java.

BitMatrix Graphplan.dependences [private]

The matrix used to store the static dependences between the operators.

Definition at line 118 of file Graphplan.java.

ArrayList<BitSet> Graphplan.facts_layers [private]

The list of facts layers of the planning graph.

Definition at line 93 of file Graphplan.java.

ArrayList<BitMatrix> Graphplan.facts_mutex [private]

The list of facts mutex of the planning graph.

Definition at line 103 of file Graphplan.java.

ArrayList<Fact> Graphplan.facts_table [private]

The list of facts of the planning problem.

Definition at line 113 of file Graphplan.java.

int Graphplan.facts_table_size [private]

The size of the facts table.

Definition at line 143 of file Graphplan.java.

long Graphplan.g_time = 0 [private]

The time spent for building graph.

Definition at line 153 of file Graphplan.java.

BitSet Graphplan.goals [private]

The bit set that represents the goal of the problem.

Definition at line 83 of file Graphplan.java.

int Graphplan.levelOff = -1 [private]

The fixed point of the planning graph.

Definition at line 123 of file Graphplan.java.

long Graphplan.m_time = 0 [private]

The time spent for computing the mutual exclusions.

Definition at line 168 of file Graphplan.java.

HashMap<Integer, Set<BitSet> > Graphplan.nogoods [private]

The table used to memorize the goals failure during search.

Definition at line 133 of file Graphplan.java.

long Graphplan.noop_tried = 0

The number of noop actions tried for finding a solution plan.

Definition at line 178 of file Graphplan.java.

int Graphplan.ops_index [private]

The index of the first operator in the operator table which is not a noops.

Definition at line 128 of file Graphplan.java.

ArrayList<BitSet> Graphplan.ops_layers [private]

The list of operators layers of the planning graph.

Definition at line 88 of file Graphplan.java.

ArrayList<BitMatrix> Graphplan.ops_mutex [private]

The list of operators mutex of the planning graph.

Definition at line 98 of file Graphplan.java.

ArrayList<Op> Graphplan.ops_table = new ArrayList<Op>(1000) [private]

The list of operators of the planning problem.

Definition at line 108 of file Graphplan.java.

int Graphplan.ops_table_size [private]

The size of the operators table.

Definition at line 148 of file Graphplan.java.

long Graphplan.p_time = 0 [private]

The time spent for preprocessing the planning problem.

Definition at line 163 of file Graphplan.java.

PDDLObject Graphplan.problem

The problem to solve.

Definition at line 78 of file Graphplan.java.

ArrayList<BitMatrix> Graphplan.resolvers [private]

The list of operators resolvers of the planning graph.

Definition at line 138 of file Graphplan.java.

long Graphplan.s_time = 0 [private]

The time spent for searching a solution plan.

Definition at line 158 of file Graphplan.java.

The documentation for this class was generated from the following file:

Graphplan.java

Public Member Functions

Static Public Member Functions

Public Attributes

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation