Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/30732
Title: Using explanation structures to speed up local-search-based planning
Authors: TIAN ZHENGMIAO
Keywords: AI, Planning, Explanation, Causal Network, Local Search, Macro-action
Issue Date: 29-Sep-2011
Source: TIAN ZHENGMIAO (2011-09-29). Using explanation structures to speed up local-search-based planning. ScholarBank@NUS Repository.
Abstract: Many examples of real-world autonomous agent applications can be found nowadays, from exploring space to cleaning floors. AI planning is a technique that is often used by autonomous agents, i.e., planning is a problem-solving task to produce a plan, which can then be performed by an autonomous agent. For example, when given a goal of ?package should be in city1?, a planning system utilizes possible actions, like ?move truck from between two cities?, ?load/unload package to/from truck?, etc., to generate a plan that is composed of a set of these actions to achieve the goal. This thesis focuses on dealing with planning systems that have loose plan structures designed to solve large-scale real-world problems. Loose plan structure involves actions in the plan that have no explicitly represented relations, like indicating that one action is added for achieving another. A lack of such causal information might result in an inefficient planning process. The goal of this thesis is to speed up planning systems that have loose plan structures using local search approaches to create plans. To address the potential inefficiencies, we propose a novel technique that uses explanation structures to retain some causal information acquired during planning. To improve the planning performance by utilizing explanation structures, we generate Multiple-In-Single-Out (MISO) causal networks, and develop algorithms to update and exploit these structures, in order to dynamically generate macro-actions and operate on them. To evaluate the proposed approach, we implemented a prototype based on a planning system named Crackpot. Our approach is promising to improve the planning performance by the usage of macro-actions.
URI: http://scholarbank.nus.edu.sg/handle/10635/30732
Appears in Collections:Master's Theses (Open)

Show full item record
Files in This Item:
File Description SizeFormatAccess SettingsVersion 
TianZM.pdf1.71 MBAdobe PDF

OPEN

NoneView/Download

Page view(s)

214
checked on Dec 11, 2017

Download(s)

230
checked on Dec 11, 2017

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.