EXCALIBUR
Adaptive Constraint-Based Agents in Artificial Environments

[LOGISTICS]   [Realization]   [Results]   [Tabu Lists]

[ Please note: The project has been discontinued as of May 31, 2005 and is superseded by the projects of the ii Labs. There won't be further updates to these pages. ]

Tabu Lists

(Related publication: [PUBLink])

Even without applying domain knowledge, there are an endless number of ways of improving the results. At least one simple way is tried below - tabu lists.

One possible way of applying a tabu list is for the global search control's constraint selection. This failed, however, in the job-shop-scheduling experiments (see Section [Tabu Lists]) and will not be tried here again.

Another possibility is to use a tabu list that stores the objects affected by changes (e.g., an Action Task moved by ARC-H2 or a Task Constraint inserted by SRC-H1). If no new object is stored in the list within an iteration (or in the case of unsuccessful application of an SRC's heuristic), an empty element is stored in the list to guarantee an ongoing replacement of the elements. A heuristic that tries to modify one of the list's objects fails to do so. The figure below shows the results for Problem 6-1.

Applying long tabu lists results in a great initial improvement. With an increasing runtime, shorter/no tabu lists prove to be better (which is irrelevant for an approach of rapid restarts). However, the use of tabu lists yields plans with a large number of actions (the figure below shows the plan-step results for the tabu-list application for Problem 6-1).

Many other `standard' methods for achieving an improvement could be tried, but this is not our main concern here.


[LOGISTICS]   [Realization]   [Results]   [Tabu Lists]

For questions, comments or suggestions, please contact us.

Last update:
May 20, 2001 by Alexander Nareyek