Fast Planning with Iterative Macros
Research on macro-operators has a long history in planning and other search applications. There has been a revival of interest in this topic, leading to systems that successfully combine macrooperators with current state-of-the-art planning approaches based on heuristic search. However, research is still necessary to make macros become a standard, widely-used enhancement of search algorithms. This article introduces sequences of macro-actions, called iterative macros. Iterative macros exhibit both the potential advantages (e.g., travel fast towards goal) and the potential limitations (e.g., utility problem) of classical macros, only on a much larger scale. A family of techniques are introduced to balance this trade-off in favor of faster planning. Experiments on a collection of planning benchmarks show that, when compared to low-level search and even to search with classical macro-operators, iterative macros can achieve an impressive speed-up in search.

title: Reinforcement Learning of Local Shape in the Game of Go
abstract: We explore an application to the game of Go of a reinforcement learning approach based on a linear evaluation function and large numbers of binary features. This strategy has proved effective in game playing programs and other reinforcement learning applications. We apply this strategy to Go by creating over a million features based on templates for small fragments of the board, and then use temporal difference learning and self-play. This method identifies hundreds of low level shapes with recognisable significance to expert Go players, and provides quantitive estimates of their values. We analyse the relative contributions to performance of templates of different types and sizes. Our results show that small, translation-invariant templates are surprisingly effective. We assess the performance of our program by playing against the Average Liberty Player and a variety of computer opponents on the 9×9 Computer Go Server. Our linear evaluation function appears to outperform all other static evaluation functions that do not incorporate substantial domain knowledge.

title: Automating Layouts of Sewers in Subdivisions
abstract: An important part of the creation of a housing subdivision is the design and layout of sewers underneath the road. This is a challenging cost optimization problem in a continuous threedimensional space. In this paper, heuristic-search-based techniques are proposed for tackling this problem. The result is new algorithms that can quickly find near optimal solutions that offer important reductions in the cost of design and construction.

title: Using Artificial Boundaries in the Game of Go
abstract: Local search in the game of Go is easier if local areas have well-defined boundaries. An artificial boundary consists of temporarily added stones that close off an area. This paper describes a new general framework for finding boundaries in a way such that existing local search methods can be used. Furthermore, by using a revised local UCT search method, it is shown experimentally that this framework increases performance on local Go problems with open boundaries.

title: Sample-based learning and search with permanent and transient memories
abstract: We present a reinforcement learning architecture, Dyna-2, that encompasses both sample-based learning and sample-based search, and that generalises across states during both learning and search. We apply Dyna-2 to high performance Computer Go. In this domain the most successful planning methods are based on sample-based search algorithms, such as UCT, in which states are treated individually, and the most successful learning methods are based on temporal-difference learning algorithms, such as Sarsa, in which linear function approximation is used. In both cases, an estimate of the value function is formed, but in the first case it is transient, computed and then discarded after each move, whereas in the second case it is more permanent, slowly accumulating over many moves and games. The idea of Dyna-2 is for the transient planning memory and the permanent learning memory to remain separate, but for both to be based on linear function approximation and both to be updated by Sarsa. To apply Dyna-2 to 9x9 Computer Go, we use a million binary features in the function approximator, based on templates matching small fragments of the board. Using only the transient memory, Dyna-2 performed at least as well as UCT. Using both memories combined, it significantly outperformed UCT. Our program based on Dyna-2 achieved a higher rating on the Computer Go Online Server than any handcrafted or traditional search based program.

title: Depth-First Discovery Algorithm for incremental topological sorting of directed acyclic graphs
abstract: We study the problem of incrementally maintaining a topological sorting in a large DAG. The Discovery Algorithm of Alpern et al.  computes a cover K f nodes such that a solution to the modified problem can be found by changing node priorities within K only. It achieves a runtime complexity that is polynomially bounded in terms of the minimal cover size k. The temporary space complexity of DA grows quickly with increasing number of added edges and cover size. We in the Depth-First Discovery Algorithm (DFDA), which uses depth-first search to reduce the temporary space of D O(|A| × ‖K‖) to O(|A| + ‖K‖), where|A| is the number of edges to add and ‖K‖ is theextended size of the cover. DFDA is simpler than DA and performs better in our empirical tests.  2003 Elsevier B.V. All rights reserved.

title: Automated Modular Termination Proofs for Real Prolog Programs
abstract: We present a methodology for checking the termination of Prolog programs that can be automated and is scalable. Furthermore, the proposed method can be used to locate errors. It has been successfully implemented as part of a tool that uses static analysis based on formal methods in order to validate Prolog programs. This tool is aimed at supporting the design and maintenance of Prolog programs.

title: PAN - The Prolog Analyzer

title: A Comparison of BPML and BPEL4WS
abstract: Web services composition receives an increasing attention as a concept to build business processes from. This paper addresses the heterogeneity of business process modeling specifications in the area of web services. A new concept called metadata relationships (MR) is introduced to describe the semantic relationship between concepts from two different XML Schemas. This approach is applied for the comparison of concepts from BPML and BPEL4WS, the two major proposals to become a standard in the area of Web Service composition. Metadata relationships are aggregated to discuss the interrelation of these two specifications. The results show that there is a large overlap between the two specifications. Therefore, an integration of them into only one specification seems feasible and desirable. 1. Comparing Business Process Modeling Methods Business Process Modeling (BPM) addresses the domain of logical dependencies of consecutive activities. In this area many different modeling methods have been developed to semantically depict these dependencies in a predefined syntax. The advantages of such formal methods are to be found in the ease of communication, the use of formal analyses, and the implementation in information systems. Business process modeling specifications in the context of Web Services provide functionality like transactions, process execution, choreography of message exchange, or exception handling. These aspects go beyond stateless communication provided by a core Web Services’ architecture built on the Simple Open Acces Protocol (SOAP) [Gu03a], [Gu03b], Web Service Description Language (WSDL) [Ch03], [Gu03c], [Mo03], and Universal Description, Discovery & Integration (UDDI) [Be02]. Such an architecture involves three parties: a service provider, a service broker, and a service requester [TP02]. WSDL is used by a service provider to describe a service which then can be published in an UDDI registry of a service broker. A service requester retrieves the WSDL document via UDDI registry and uses it for binding. Messages are exchanged via SOAP. All these standards are based on the eXtensible Markup Language (XML) [Br00] allowing an easy transportation on top of common Internet protocols like HTTP. Various specifications have been proposed for BPM of Web Services . The Business Process Execution Language fro Web Services ( BPEL4WS) [An03], the Business Process Modeling Language (BPML)  are proposals dedicated to the composition of various Web Services to become a business process. The ebXML Business Process Specification Schema (BPSS) [UN01], the Web Service Choreography Interface (WSCI) [Ar02b], and the Web Service Conversation Language (WSCL) [Ba02] deal with choreography or conversation, that is the allowed sequence of message exchanges from an external point of view. All of these languages offer an XML-based syntax and they are specially developed to address requirements in the area of WS. Yet, the the expressive power of these specifications are too little investigated with respect to a common benchmark. Van der Aalst et al. use so called workflow and communication patterns and express them with concepts of BPML [Aa02] and BPEL4WS [Wo02]. But in order to better understand these two proposals , transformations are needed that map constructs of their meta model to other better known concepts. The DARPA Agent Markup Language – Services (DAML-S) [DA03] seems to be a natural candicate by developing a extensive ontology on Web Services. This paper complements the efforts of DAML-S by comparing the expressive power of BPML and BPEL4WS activities . Since the merger of WSFL and XLANG to become BPEL4WS they are the two major candidates to gain the status of a standard for Web Service composition. Both of these vocabularies are expressed in XML, permitting the comparison of their metadata, which are elements and attributes defined by their respective XML Schemas [Be01], [BM01]. In section 2 a new approach is introduced called metadata relationships (MR) and schema relationships (SR). This allows for a semi-formal, but in depth analysis of the semantic interrelation of metadata elements from two different schemas. Section 3 discusses metadata relations (MR) between activities supported in BPML and BPEL4WS. The final section outlines future research. 2. Metadata Relationships and Schema Relationships 2.1. Metadata Relationships on the Micro Level The integration of data from different metadata schemas has been discussed since the advent of database systems. Classifications of potential conflicts have been proposed by [CW93] and [SPD92] to name but a few. Generally, a micro and a macro perspective can be distinguished. The micro perspective refers to conflicts due to different representations of concepts in two schemas. The macro perspective allows statements about the relation of entire schemas. We introduce Metadata Relationships (MR) as a concept on the micro level. MR refer to how concepts of a schema A are related to concepts from another schema B. Such concepts are identified by metadata elements of the respective XML Schema or DTD. Accordingly, we define a Metadata-Set MA of a schema A as a set of all elements and attributes that are defined in the XML Schema or DTD of A. A MR(a,b) is formally defined for a ⊆ MA and b ⊆ MB. MR may be of eight different types: the first three are called symmetric MR, the next three are called asymmetric MR, and the last two are called incomplete MR. The symmetric MR are related to cardinalities known from Entity-Relationship Diagrams [Ch76]. But in contrast to ERD cardinalities that refer to relations between entities in one single schema, MR refer to relations between concepts from two different schemas. Symmetric MR describe the situation when a concept a ⊆ MA from one schema A can always be mapped to a concept b ⊆ MB from the other schema B, and when this concept b can also always be mapped to the same concept a of the first schema. From this follows that symmetric MR allow bidirectional transformations. Asymmetric MR permit only one way transformations without loss of information. Incomplete MR refer to concepts that partially intersect or that are not included in the other schema at all. 1. Symmetric MR(1:1) 1:1-MR refer to concepts from different schemas that are semantically equivalent. This MR addresses naming and domain conflicts as describes by Ceri et al. [CW93]. An example would be “Auto” from a German schema G and “Car” from an English schema E. We then write MR(G.Auto, ) = MR(1:1). 2. Symmetric MR(1:N) 1:N-MR address the problem of different levels of abstraction of two concepts. Things may be modeled in terms of data of metadata leading to meta-data conflicts [CW93]. Note, that a MR can only be symmetric when concepts b1, b2,...,bn of the second schema B describe a partition over the concept a of the first schema A. If there is a residue from the intersection of both sets of concepts, no round trip is possible without loss of information. For example, take two different schemas called A and B. A only knows the general concept of “parent”, B distinguished between “mother” and “father”. Then, a “parent” of A can always be mapped to either “mother” or “father” from schema B, and “mother” and “father” can always be mapped to “parent”. The concepts address the same set of instances without residue. A round-trip is possible without loss of information. The actual decision whether a parent is a mother or a father cannot be taken on the level of metadata, it depends on additional information from the data level. We write MR(A.parent, {B.father, B.mother}) = MR(1:N). 3. Symmetric MR(N:M) The N:M-MR is similar to the 1:N-MR, but now both schemas describe a partition of one and the same concept, that is not explicitly modeled in both schemas. An example may be a schema P1 that differentiates between male and female, and another schema P2 distinguishing between minors and adults. Both describe a partition of people. Using additional information from the data level, the metadata concepts can be mapped. We write MR ({P1.male, P1.female}, {P2.minor, P2.adults}) = MR(N:M). 4. Asymmetric MR(1:X) The asymmetric 1:X-MR describes a concept that is a subset of the second concept. On the one hand, this allows for a transformation from the first concept to the second concept without loss of information. On the other hand, a transformation from the second concept to the first one leads to a loss of information, because not all instances can be expressed in terms of the first schema. Take a schema A that explicitly models the concept “bus”, and a second schema B with a concept “car”. All instances of bus are also instances of the concept car. But not all instances from car are also busses, leading to a loss of information when there is a transformation from B.car to A.bus. We write MR(A.bus, B.car) = MR(1:X). 5. Asymmetric MR(N:X) The N:X-MR is similar to the 1:X-MR. Imagine schema A also containing a concept called “truck”. There is a 1:X-MR between A.bus and B.car, and also between A.truck and B.car. The N:X-MR is an abbreviation for this which allows to capture all to B.car related concepts of A in one expression. We write MR({A.bus, A.truck}, B.car) = MR(N:X). 6. Asymmetric MR(1:S) The 1:S-MR refers to a subcomponent-relation or a definition. Concepts of the first schema can be simulated in terms of a block of concepts from the other schema. For example take a schema A.route and a schema B with the concept street. The concept route captures the semantics of a certain sequence of streets to follow in order to get from one place to another. This allows A.route to be simulated by a set of B.streets, but streets cannot be expressed in terms of schema A’s route. We write MR(A.route, B.street) = MR(1:S) 7. Incomplete MR(X:Y) The X:Y-MR describes intersecting concepts with none of both being a subset of the other. Fo