Optimisation and relaxation for multiagent planning in the situation calculus

Toby O. Davies, Adrian R. Pearce, Peter J. Stuckey, Harald Søndergaard

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

Abstract

The situation calculus can express rich agent behaviours and goals and facilitates the reduction of complex planning problems to theorem proving. However, in many planning problems, solution quality is critically important, and the achievable quality is not necessarily known in advance. Existing Golog implementations merely search for a Legal plan, typically relying on depth-first search to find an execution. We illustrate where existing strategies will not terminate when quality is considered, and to overcome this limitation we formally introduce the notion of cost to simplify the search for a solution. The main contribution is a new class of relaxations of the planning problem, termed precondition relaxations, based on Lagrangian relaxation. We show how this facilitates optimisation of a restricted class of Golog programs for which plan existence (under a cost budget) is decidable. It allows for tractably computing relaxations to the planning problem and leads to a general, blackbox, approach to optimally solving multi-agent planning problems without explicit reference to the semantics of interleaved concurrency.

Original languageEnglish
Title of host publicationAAMAS'15 - Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems
Subtitle of host publicationMay, 4-8, 2018, Istabul, Turkey
EditorsRafael H. Bordini, Edith Elkind
Place of PublicationNew York NY USA
PublisherInternational Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)
Pages1141-1149
Number of pages9
ISBN (Electronic)9781450337700, 9781450334136
Publication statusPublished - 2015
Externally publishedYes
EventInternational Conference on Autonomous Agents and Multiagent Systems 2015 - Istanbul, Turkey
Duration: 4 May 20158 May 2015
Conference number: 14th
http://www.ifaamas.org/AAMAS/aamas2015/

Conference

ConferenceInternational Conference on Autonomous Agents and Multiagent Systems 2015
Abbreviated titleAAMAS 2015
CountryTurkey
CityIstanbul
Period4/05/158/05/15
Internet address

Keywords

  • Golog
  • Lagrangian relaxation
  • Resource-bounded planning
  • Situation calculus

Cite this