Action Elimination and Plan Neighborhood Graph Search: Two Algorithms for Plan Improvement
Compared to optimal planners, satisficing planners can solve much harder problems but may produce overly costly and long plans. Plan quality for satisficing planners has become increasingly important. The most recent planning competition IPC-2008 used the cost of the best known plan divided by the cost of the generated plan as an evaluation metric. This paper proposes and evaluates two simple but effective methods for plan improvement: Action Elimination improves an existing plan by repeatedly removing sets of irrelevant actions. Plan Neighborhood Graph Search finds a new, shorter plan by creating a plan neighborhood graph PNG(π) of a given plan π, and then extracts a shortest path from PNG(π). Both methods are implemented in the ARAS postprocessor and are empirically shown to improve the result of several planners, including the top four planners from IPC-2008, under competition conditions.

title: Game-SAT: A Preliminary Report
abstract: Game-SAT is a 2-player version of SAT where two players (MAX and MIN) play on a SAT instance by alternatively selecting a variable and assigning it a value true or false. MAX tries to make the formula true, while MIN tries to make it false. The Game-SAT problem is to determine the winner of a SAT instance under the rules above, assuming the perfect play by both players. The Game-SAT problem, originally derived from an application in adversarial planning, is PSPACE-complete. The problem is similar to QBF, but differs by the property of free variable selection, compared to QBF with its fixed variable ordering. We have developed a Game-SAT solver, Gasaso, that uses a combination of standard game tree search techniques, search methods that are well known in the SAT community, and specialized pruning techniques. We show empirically how the solver performs in this new domain, and give evidence for the existence of phase transitions in this problem.

title: Fast Planning with Iterative Macros
abstract: 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: 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: Weblogs, Legitimacy and Organizations
abstract: The last decades have seen a movement of production to less economically developed countries. These countries often don’t meet Western social and environmental standards. Non-governmental organizations (NGOs) have challenged poor conditions such as child labor, discrimination or environmental pollution caused by suppliers. Purchasers are criticized in the public realm, which leads to damage to their reputation [Hansen and Schrader 2005; Gilbert 2003]. Nike, Dole Foods and GM have experienced such campaigns [Lawrence 2002]. Focal companies with direct contact to the end customer and big labels are most vulnerable to this strategy. A loss of reputation may weaken their ability to compete and result in decreasing sales volume [Hansen and Schrader 2005].

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