15151397
Logical Properties of Belief-Revision-Based Bargaining Solution
This paper explores logical properties of belief-revision-based bargaining solution. We first present a syntax-independent construction of bargaining solution based on prioritized belief revision. With the construction, the computation of bargaining solution can be converted to the calculation of maximal consistent hierarchy of prioritized belief sets. We prove that the syntax-independent solution of bargaining satisfies a set of desired logical properties for agreement function and negotiation function. Finally we show that the computational complexity of belief-revision-based bargaining can be reduced to $\Delta^P_2[\mathcal{O}(\log n)]$.
1042778
Axiomatic Analysis of Negotiation Protocols
This paper presents an axiomatic approach to negotiation protocol analysis. We consider a negotiation procedure as multiple stages of mutual belief revision. A set of postulates in AGM-style of belief revision are proposed to specify rational behavior of negotiation. An explicit construction of negotiation function is given in which negotiation process is viewed as the interaction of two iterated revision operations. As a result the proposed axiomatic system is proved to be consistent. Finally, we examine our approach with an instantiation of Rosenschein and Zlotkin’s Monotonic Concession Protocol of Negotiation.
8370711
Consistency of Action Descriptions
As a contribution to the metatheory of reasoning about actions, we present some characteristics of the consistency of action theories. Three levels of consistency are investigated for the evaluation of action descriptions: uniform consistency, consistency of formulas and regional consistency. The first two provide an intuitive resolution of problems of explanation conflicts and fluent dependency. The concept of regional consistency provides for a measure of ramification. A highly expressive form of action descriptions, the normal form, is introduced to facilitate this analysis. The relative satisfiability of the situation calculus is generalized to accommodate non-deterministic effects and ramifications.
1234389
Nonmonotonic Reasoning and Multiple Belief Revision
The aim of the present paper is to reveal the interrelation between general patterns of nonmonotonic reasoning and multiple belief revision. For this purpose we de ne a nonmonotonic inference frame in which individual inference rules have been proposed in the literature but their combination as a system has not been investigated. It is shown that such a system is so strong that almost all the rules (including the supracompactness) suggested for nonmonotonic inference relations in the literature hold in it. We prove that this nonmonotonic inference frame is strictly correspendent with multiple belief revision operation. On the basis of this result we analyse a speci c paradigm of defult theory which satis es all the rules under consideration and discuss limitations of methods based on consequence relations for the study of nonmonotonic reasoning.
35603840
State Minimization Re-visited
A well-known circumscription policy in situation calculus theories of actions is to minimize the Abnormality predicate by varying the Holds predicate. Unfortunately this admitted counter-intuitive models. A different policy of varying the Result function eliminated these models. Explanations of how it did this are not entirely satisfactory, but seem to appeal to informal notions of state minimization. We reexamine this policy and show that there are simple justifications for it that are based on classical automata theory. It incidentally turns out that the description "state minimization" for the varying Result policy is more accurate than the original nomenclature had intended.
9693532
Negotiation mechanism for TAC SCM component market
This paper presents a new negotiation mechanism and a new supplier model for Trading Agent Competition Supply Chain Management(TAC SCM). Under the new negotiation mechanism, an agent is allowed to negotiate with component suppliers on price, delivery date and supply quantity while a supplier can autonomously vary its production capacity with market demands and allocate its products to buyers through auction. A mathematical analysis is given to ensure the new negotiation mechanism and supplier model effectively solve the existing problems while keeping most good features of the original TAC SCM game model.
2785687
Close pair queries in moving object databases
Databases of moving objects are important for air traffic control, ground traffic, and battlefield configurations. We introduce the (historical and spatial) range close-pair query for moving objects as an important problem for such databases. The purpose of a range close-pair query for moving objects is to find pairs of objects that were closer than ε during time interval $I$ and within spatial range R, where ε, I and R are user-specified parameters.This paper solves the range close-pair query using two components: the retrieval component and the close-pair identification component. The retrieval component breaks up long trajectories into trajectory segments, which are produced in increasing time order, without the need for sorting. The retrieval component takes advantage of a new index mechanism, the Multiple TSB-tree. The segments are then pipelined to the close-pair identification component. The identification component introduces a novel spatial sweep that sweeps by time and one spatial dimension at the same time. Extensive experimental results are provided, demonstrating the advantages of the new approach when considering close pairs.
206133548
An efficient algorithm to rank Web resources
Abstract How to rank Web resources is critical to Web Resource Discovery (Search Engine). This paper not only points out the weakness of current approaches, but also presents in-depth analysis of the multidimensionality and subjectivity of rank algorithms. From a dynamics viewpoint, this paper abstracts a user's Web surfing action as a Markov model. Based on this model, we propose a new rank algorithm. The result of our rank algorithm, which synthesizes the relevance, authority, integrativity and novelty of each Web resource, can be computed efficiently not by iteration but through solving a group of linear equations.
3129003
Efficient computation of temporal aggregates with range predicates
A temporal aggregation query is an important but costly operation for applications that maintain time-evolving data (data warehouses, temporal databases, etc.). Due to the large volume of such data, performance improvements for temporal aggregation queries are critical. In this paper we examine techniques to compute temporal aggregates that include key-range predicates (range temporal aggregates). In particular we concentrate on SUM, COUNT and AVG aggregates. This problem is novel; to handle arbitrary key ranges, previous methods would need to keep a separate index for every possible key range. We propose an approach based on a new index structure called the Multiversion SB-Tree, which incorporates features from both the SB-Tree and the Multiversion B-Tree, to handle arbitrary key-range temporal SUM, COUNT and AVG queries. We analyze the performance of our approach and present experimental results that show its efficiency.
34860384
Computer Simulation Study on Central Pattern Generator: from Biology to Engineering
Central pattern generator (CPG) is a neuronal circuit in the nervous system that can generate oscillatory patterns for the rhythmic movements. Its simplified format, neural oscillator, is wildly adopted in engineering application. This paper explores the CPG from an integral view that combines biology and engineering together. Biological CPG and simplified CPG are both studied. Computer simulation reveals the mechanism of CPG. Some properties, such as effect of tonic input and sensory feedback, stable oscillation, robustness, entrainment etc., are further studied. The promising results provide foundation for the potential engineering application in future.
9840052
Finding Fastest Paths on A Road Network with Speed Patterns
This paper proposes and solves the Time-Interval All Fastest Path (allFP) query. Given a user-defined leaving or arrival time interval I, a source node s and an end node e, allFP asks for a set of all fastest paths from s to e, one for each sub-interval of I. Note that the query algorithm should find a partitioning of I into sub-intervals. Existing methods can only be used to solve a very special case of the problem, when the leaving time is a single time instant. A straightforward solution to the allFP query is to run existing methods many times, once for every time instant in I. This paper proposes a solution based on novel extensions to the A* algorithm. Instead of expanding the network many times, we expand once. The travel time on a path is kept as a function of leaving time. Methods to combine travel-time functions are provided to expand a path. A novel lower-bound estimator for travel time is proposed. Performance results reveal that our method is more efficient and more accurate than the discrete-time approach.