Having had a Yaroze since they were first released in the UK, I’ve now finally gotten around to setting up a home page. Attached are the code and dissertation for my final year project that enabled me to successfully complete a Masters Degree with the Open University. The project uses the Yaroze Playstation to evaluate the performance of Scott Penberthy and Daniel Weld’s partial-order UCPOP Artificial Intelligence Planning Algorithm* against a Dynamic Environment.

The evaluation Environment constructed on the Yaroze consists of an Agent that aims to apply Actions to manipulate the Environment into a desired Goal State, which in this case was to enable the Agent to reach an Exit location by overcoming obstacles in its way. The Agent generates a Plan by adding together a series of Actions such as Moving to a Location, Picking up a Key, or Opening a Door, that ultimately achieve the Preconditions of reaching the Goal State – e.g. the Agent arriving at the Exit location.

A Door, a Key and the Exit:-

The most complex Environment scenario that the Agent has to Plan to traverse:-

Once the Agent has constructed a Plan it endeavours to execute it against the Environment. Against a Static Environment a Plan that achieves the Agent Goal will always execute successfully as Agent Actions are the only means of changing the Environment State – there are no outside influences. But the Environment being evaluated is Dynamic rather than Static and the Agent may therefore find that the Environment State has changed since its Plan was generated. With the Environment in a changed State the Agent’s Plan may well become outdated and fail as the Preconditions for executing the remaining Actions no longer exist. In this situation the Agent is forced to recover from the failure by re-generating a Plan to meet the outstanding Preconditions of the Goal State. The Dynamic events within the Environment are represented by Bridges that raise and lower automatically, thereby enabling or barring the Agent’s movement over stretches of water.

A Bridge:-

Another important concept that the project considered was that of Time. Classical AI Planning theory assumes that the acts of generating a Plan and applying Actions are executed instantaneously. This isn’t the case in the real-world and the project therefore assigns a Time Cost to both Plan generation (the Time it takes to construct a Plan) and Action execution (the Time it takes to apply the Effects of an Action to the Environment). The abstract concept of ‘Turns’ is used to represent the passage of Time.

The project evaluated the implementation of the UCPOP algorithm against a number of differing scenarios. Three factors were varied to allow data about Plan generation and execution to be gathered from 27 scenarios. The three factors were:-

· The complexity of the Environment, represented by the percentage of accessible/inaccessible locations plus the number of objects within the Environment.

· The rate at which Dynamic events occurred within the Environment.

· The location at which the Agent started the scenario.

From each of the scenarios metric information about the number and complexity of the Plans constructed by the Agent was gathered for analysis.

Technically, the project includes:-

· An implementation of the UCPOP AI Planner that allows the Agent to generate Plans to meet its Goals.

· A best-first, depth limited, memory constrained search algorithm that the Agent uses for path-finding around the Environment.

· Code to execute the Plan, once it has been generated, against the Dynamic Environment.

The project does NOT include:-

· Optimised code. The emphasis of the project was on academic research rather than the implementation of optimised code. The code is merely a means to extract the scenario data for analysis and deduction in the Dissertation.

· The Metrowerks Linker also gave me a great deal of grief when passing parameters to a function in a separate C source file. This was overcome with a botch using global variables. (Effective, but not particularly graceful!).

Please feel free to drop me an email if you have any questions.

Regards,

Brian Warner

Email: bwarner@dial.pipex.com

Last Updated: 29 December 2001.

* Penberthy, J.S. and Weld, D.S. (1992) UCPOP: A Sound, Complete, Partial Order Planner for ADL, Morgan Kaufmann in Principles of Knowledge Representation and Reasoning – Proceedings of the Third International Conference.