 |
Publications |
|
|
|
|
|
|
 Allen, T.L. |
|
Time-optimal active decision making
PhD thesis, The University of Sydney, Apr, 2011
|
Abstract
This thesis describes a class of problems known as Time-Optimal Active Decision Making (TOADM). The objective of TOADM problems is to make decisions and act upon them in order to achieve a goal, and to do so in the minimum total time. This total time includes both the time taken to make decisions, and the time taken to act upon them. Such problems exhibit three key features. Firstly, they make decisions and act at the same time; the decisions are `active' because they are made while the system is operational. Secondly, the performance of the system is influenced by the time taken to compute decisions during its operation. Thirdly, successful operation requires the achievement of a goal in unbounded time, but improved performance can be obtained by doing so in less time.
TOADM problems arise in many disciplines, but the principle example used throughout this thesis is Time-Optimal Planning and Execution (TOPE) for autonomous agents. This problem requires an agent to travel from its initial location to a specified goal, and to do so safely and in as little time as possible. In this case, the total time includes both the time spent computing the plans used to guide the agent and the time spent executing them. Since the state space of the agent can be dynamic, a trade-off must be made between computing efficient plans slowly, and inefficient plans quickly.
This thesis derives a framework for solving general TOADM problems, and demonstrates its application to the TOPE problem. The technique involves estimating the set of system parameters that specify the best trade-off between the time required to make decisions and the time required to act upon them. Since the state space of the decision making process can be dynamic, these estimates must be continually recomputed, and the parameters continually adjusted while the system is in operation. These system parameters are entirely application dependent, but include any run-time adjustable features of the system that affect this trade-off. It is shown that time-optimal behaviour is obtained when the parameter set is selected such that the expected total time is minimised, and that this total time is the sum of the expected time to make the parameter set selection,the expected time to make a decision given this parameter set, and the expected time to achieve a goal given this decision.
Unfortunately, selection of the optimum parameter set is known to be an intractable problem, and is made even more difficult in cases such as the TOPE problem where even the assessment of a single choice of parameter set is itself an intractable problem. Experiments are performed which demonstrate that if this selection can be performed sufficiently fast and accurately, it is possible to improve upon the performance of any technique which uses a fixed set of parameters. This is true even when this parameter set is the optimal fixed choice (determined by a brute-force analysis that is unavailable in most practical applications).
The TOADM framework is implemented for the TOPE problem, where the trade-off is between the time required to compute plans, and the time required to execute them. The available system parameters include the resolution of a discrete representation of the operating environment, and variables affecting the behaviour of the planning algorithms used. The final set of experiments verifies that it is possible to implement two categories of parameter selection techniques that achieve sufficient accuracy and timeliness. The experiments show that several selection techniques are able to outperform all fixed parameter techniques, and even techniques with additional information about the scenario. It is also shown that there exist scenarios where fixed parameter techniques are completely unsuitable. Although the simplest types of selection techniques are also unsuited to these scenarios, others remain able to significantly outperform all alternative techniques and approach the theoretical bounds on performance.
|
| Download |
PDF full text (27.43M)
|
|
Copyright Notice & Disclaimer |
|