[mercury-users] Tech Report: ``Efficient Knowledge and Action Planning in First Order Logic''

[Ralph Becket]

People on this mailing list might be interested in this...

I've finally got around to tarting up my thesis and making it
available as a technical report.  You can find .pdf and .ps versions
of it here as ``Report CRC-075'':

http://www.cam.sri.com/tr/ABSTRACTS.html

Any feedback will be gratefully received.

Here's the abstract:

	This thesis describes an efficient method of plan construction
	for solving knowledge and action planning problems in a first
	order framework.  Classical planning has concentrated on
	purely action based problems where sufficient information is
	available at plan time to completely specify a sequence of
	actions sufficient to achieve the goal.  That is, the
	execution of the tasks prescribed in the plan is independent
	of the state of the world at run time.  Hence classical plans
	are specifications for programs in which control flow is
	entirely linear and the arguments to all actions are
	constants.  Knowledge and action goals arise when the planner
	does not have sufficient information to be able to create such
	a plan.  Instead, the planner must construct plans which
	specify how information is to be obtained and exploited to
	achieve the goal.  The simplest form of knowledge and action
	plan involves an input, or knowledge gathering, action and
	another whose behaviour depends upon the input (e.g.  looking
	up someone's phone number in the telephone directory in order
	to dial it).  More complex knowledge and action goals can only
	be solved by programs with conditional and/or iterative
	control flow.  Moreover, such goals often include constraints
	on what is to be done that are not achievable.  This thesis
	describes a novel type of hierarchical task network planning,
	based on the notion of planning as implicative translation,
	for the construction of knowledge and action plans.
	Implicative translation views plans as logical formulae and
	planning as refinement to a more specific formula.  Plans may
	contain input tasks, explicit reference to the executive's
	state at run time, disjunction, existential quantification and
	a limited form of universal quantification.  Plans generated
	specify events and tasks which must be successfully executed
	in order to reach the goal.  However, program generation from
	plan specifications is complicated by the need to detect when
	conditional and iterative control flow is required.  Since
	most real-world information sources are either noisy or
	incomplete, planning seeks to maximise completeness (for
	universally quantified goals), efficiency and likelihood of
	success.  Finally, a planner, Baldric, implemented using the
	framework is described in detail.

"A rip-snorting, blinder of a first novel.  Chapter eight was
particularly exciting." (The Times Literary Supplement).

-- 
Ralph Becket  |  rwab1 at cam.sri.com  |  http://www.cam.sri.com/people/becket.html

----- End forwarded message -----

-- 
Ralph Becket  |  rwab1 at cam.sri.com  |  http://www.cam.sri.com/people/becket.html
--------------------------------------------------------------------------
mercury-users mailing list
post:  mercury-users at cs.mu.oz.au
administrative address: owner-mercury-users at cs.mu.oz.au
unsubscribe: Address: mercury-users-request at cs.mu.oz.au Message: unsubscribe
subscribe:   Address: mercury-users-request at cs.mu.oz.au Message: subscribe
--------------------------------------------------------------------------