Conventionally, most network protocols assume that the network entities who participate in the network activities will always behave as instructed. However, in practice, most network entities are selfish: they will try to maximize their own benefits instead of altruistically contributing to the network by following the prescribed protocols. Thus, new protocols should be designed for the non-cooperative network that is composed of selfish entities. In this paper, we specifically show how to design truthful multicast protocols for non-cooperative networks such that these selfish entities will follow the protocols out of their own interests. By assuming that every entity has a fixed cost for a specific multicast, we give a general framework to decide whether it is possible and how, if possible, to transform an existing multicast protocol to a truthful multicast protocol by designing a proper payment protocol. We then show how the payments to those relay entities are shared fairly among all receivers so that it encourages collaboration among receivers. As running examples, we show how to design truthful multicast protocols for several multicast structures that are currently used in practice.

This paper presents several results on some cost-minimizing path problems in polygonal regions. For these types of problems, an approach often used to compute approximate optimal paths is to apply a discrete search algorithm to a graph G(epsilon) constructed from a discretization of the problem; this graph is guaranteed to contain an epsilon-good approximate optimal path, i.e., a path with a cost within (1 + epsilon) factor of that of an optimal path, between given source and destination points. Here, epsilon > 0 is the user-defined error tolerance ratio. We introduce a class of piecewise pseudo-Euclidean optimal path problems that includes several non-Euclidean optimal path problems previously studied and show that the BUSHWHACK algorithm, which was formerly designed for the weighted region optimal path problem, can be generalized to solve any optimal path problem of this class. We also introduce an empirical method called the adaptive discretization method that improves the performance of the approximation algorithms by placing discretization points densely only in areas that may contain optimal paths. It proceeds in multiple iterations, and in each iteration, it varies the approximation parameters and fine tunes the discretization.

Differentiated service (DiffServ) is a mechanism to provide the quality-of-service (QoS) with a certain performance guarantee. In this paper, we study how to design DiffServ multicast when every relay link is an independent selfish agent. We assume that each link e/sub i/ is associated with a (privately known) cost coefficient c/sub i/ such that the cost of e/sub i/ to provide a transmission service with bandwidth demand x is c/sub i//spl middot/x. Further, we assume that there is a fixed source node s and a set R of receivers, each of which requires from s data with a minimum bandwidth demand. The DiffServ multicast problem is to compute a link-weighted tree rooted at s and spanning R such that the receivers' demands are met. This generalizes the traditional link-weighted Steiner tree problem. We first show that a previous approximation algorithm does not directly induce a strategyproof mechanism. We then give a new polynomial time algorithm to construct a DiffServ multicast tree whose total cost is no more than eight times the optimal total cost when the cost coefficient of each link is known. Based on this tree, we design a truthful mechanism for DiffServ multicast, i.e., we give a polynomial-time computable payment scheme to compensate all chosen relay links such that each link maximizes its profit when it declares its cost coefficient truthfully.

Conventionally, most network protocols assume that the network entities that participate in the network activities will always behave as instructed. However, in practice, most network entities will try to maximize their own benefits instead of altruistically contribute to the network by following the prescribed protocols, which is known as selfish. Thus, new protocols should be designed for the non-cooperative network, which is composed of selfish entities. In this paper, we specifically show how to design strategyproof multicast protocols for non-cooperative networks such that these selfish entities will follow the protocols out of their own interests. By assuming that a group of receivers is willing to pay to receive the multicast service, we specifically give a general framework to decide whether it is possible, and how if possible to transform an existing multicast protocol to a strategyproof multicast protocol. We then show how the payments to those relay entities are shared fairly among all receivers so that it encourages collaboration among receivers. As a running example, we show how to design the strategyproof multicast protocol for the currently used core-based multicast structure. We also conduct extensive simulations to study the relations between payment and cost of the multicast structure.

% '& ( " ) * ,+ .-/0 ,1 ,+ 2 0 " 3 ,4 5 76 8 :9 ; 6 =< > (4 ?A@ B? BC D9 E F G; H I J? AK L6 8 NM F 0K L6 8

Probabilistic roadmap (PRM) planners have been successful in path planning of robots with many degrees of freedom, but sampling narrow passages in a robot's configuration space remains a challenge for PRM planners. This paper presents a hybrid sampling strategy in the PRM framework for finding paths through narrow passages. A key ingredient of the new strategy is the bridge test, which reduces sample density in many unimportant parts of a configuration space, resulting in increased sample density in narrow passages. The bridge test can be implemented efficiently in high-dimensional configuration spaces using only simple tests of local geometry. The strengths of the bridge test and uniform sampling complement each other naturally. The two sampling strategies are combined to construct the hybrid sampling strategy for our planner. We implemented the planner and tested it on rigid and articulated robots in 2-D and 3-D environments. Experiments show that the hybrid sampling strategy enables relatively small roadmaps to reliably capture the connectivity of configuration spaces with difficult narrow passages.

We discuss the problem of computing optimal paths on terrains for a mobile robot, where the cost of a path is defined to be the energy expended due to both friction and gravity. The physical model used by this problem allows for ranges of impermissible traversal directions caused by overturn danger or power limitations. The model is interesting and challenging, as it incorporates constraints found in realistic situations, and these constraints affect the computation of optimal paths. We give some upper- and lower-bound results on the combinatorial size of optimal paths on terrains under this model. With some additional assumptions, we present an efficient approximation algorithm that computes for two given points a path whose cost is within a user-defined relative error ratio. Compared with previous results using the same approach, this algorithm improves the time complexity by using 1) a discretization with reduced size, and 2) an improved discrete algorithm for finding optimal paths in the discretization. We present some experimental results to demonstrate the efficiency of our algorithm. We also provide a similar discretization for a more difficult variant of the problem due to less restricted assumptions.

Probabilistic roadmap (PRM) planners have been successful in path planning of robots with many degrees of freedom, but narrow passages in a robot's configuration space create significant difficulty for PRM planners. This paper presents a hybrid sampling strategy in the PRM framework for finding paths through narrow passages. A key ingredient of the new strategy is the bridge test, which boosts the sampling density inside narrow passages. The bridge test relies on simple tests of local geometry and can be implemented efficiently in high-dimensional configuration spaces. The strengths of the bridge test and uniform sampling complement each other naturally and are combined to generate the final hybrid sampling strategy. Our planner was tested on point robots and articulated robots in planar workspaces. Preliminary experiments show that the hybrid sampling strategy enables relatively small roadmaps to reliably capture the connectivity of configuration spaces with difficult narrow passages.

In this paper we discuss the problem of computing optimal paths on terrains for a mobile robot. The cost of a path is defined to be the energy expended due to both friction and gravity. The model allows for ranges of impermissible traversal directions caused by overturn danger or power limitations. This model is interesting and challenging as it incorporates constraints found in realistic situations and these constraints affect the computation of optimal paths. We give some upper and lower bound results on the combinatorial size of energy-minimizing paths on terrains. We also present an efficient approximation algorithm that computes for two given points a path whose cost is within a user-defined relative error ratio. Compared to previous results with the same approach, this algorithm improves the time complexity by using: (1) a discretization with reduced size, and (2) an improved discrete algorithm for finding optimal paths in the discretization. We present some preliminary experimental results to demonstrate the efficiency of our algorithm. We also provide a similar discretization for the same model but under less restricted assumptions.

In this paper we define a class of mechanical systems consisting of rigid objects (defined by linear or quadratic surface patches) connected by frictional contact linkages between surfaces. (This class of mechanisms is similar to the analytical engine developed by Babbage in the 1800s, except that we assume frictional surfaces instead of toothed gears.) We prove that a universal Turing Machine (TM) can be simulated by a (universal) frictional mechanical system in this class consisting of a constant number of parts. Our universal frictional mechanical system has the property that it can reach a distinguished final configuration through a sequence of legal movements if and only if the universal TM accepts the input string encoded by its initial configuration. There are two implications from this result. First, the robotic mover's problem is undecidable when there are frictional linkages. Second, a mechanical computer can be constructed that has the computational power of any conventional electronic computer and yet has only a constant number of mechanical parts. Previous constructions for mechanical computing devices (such as Babbage's analytical engine) either provided no general construction for finite state control or the control was provided by electronic devices (as was common in electromechanical computers such as Mark I subsequent to Turing's result). Our result seems to be the first to provide a general proof of the simulation of a universal TM via a purely mechanical mechanism. In addition, we discuss the universal frictional mechanical system in the context of an error model that allows an error up to $\epsilon$ in each mechanical operation. We first show that, for a universal TM M, a frictional mechanical system in this $\epsilon$-error model can be constructed such that, given any space bound S, the system can simulate the computation of M on any input string $\omega$ if M decides $\omega$ in space bound S, provided that $\epsilon < 2^{-cS}$ for some constant c. We also show that, for any universal TM M and space bound S, there exists a frictional mechanical system in the $\epsilon$-error model with $\epsilon = \Omega(1)$; it has O(S) parts and can simulate M on any input $\omega$ that M decides in space bound S.

The results discussed in this paper are relevant to a large database consisting of consumer profile information together with behavioral (transaction) patterns. We introduce the concept of profile association rules, which discusses the problem of relating consumer buying behavior to profile information. The problem of online mining of profile association rules in this large database is discussed. We show how to use multidimensional indexing structures in order to actually perform the mining. The use of multidimensional indexing structures to perform profile mining provides considerable advantages in terms of the ability to perform very generic range-based online queries.