Assistance networks for dynamic multirobot tasks

In this paper, we consider dynamic multirobot tasks that can be done by any of the robots, but only with the assistance of any other robot. We propose a novel approach based on the concept of ‘assistance networks’ with two complementary aspects, namely assistant finding and network topology update. Each robot, encountering a new task, seeks an assisting robot among its immediate neighbors in the assistance network in a decentralized manner. The network topology is defined based on pairwise stability via payoff functions that consider general task-related guidelines. As such, the number of potential assisting robots can be ensured a priori depending on tasks’ requirements. As robots move around, the topology is updated via pairwise games. If the games are conducted by a network coordinator, each game is shown to result in a pairwise stable network. A series of simulation and experimental results in a variety of different scenarios demonstrate that the robots are able to get assistance or give assistance flexibly.     

基于博弈论的SDN弹性控制机制研究

交换机在不同控制域之间迁移可以消除软件定义网络（SDN）中过载的控制器,过载控制器将部分交换机迁移到其邻居域需要判断迁移哪些交换机及目标控制器。首先将源目的控制器间的交互关系建模为两人非合作博弈,每个博弈参与者独立地选择策略并同时发布,通过设计合理的支付函数,该博弈存在纯策略纳什均衡。设计了一种基于非合作博弈的过载控制器消除算法(Overloaded Controller Eliminated Algorithm,OCEA),由于不同的博弈活动之间是独立进行的,因此OCEA可以合成为一种分布式的方法。最后,通过原型实现了GAME-SM,验证了算法的有效性。     

Bounded budget betweenness centrality game for strategic network formations

In computer networks and social networks, the betweenness centrality of a node measures the amount of information passing through the node when all pairs are conducting shortest path exchanges. In this paper, we introduce a strategic network formation game in which nodes build connections subject to a budget constraint in order to maximize their betweenness in the network. To reflect real world scenarios where short paths are more important in information exchange in the network, we generalize the betweenness definition to only count shortest paths with a length limit ? in betweenness calculation. We refer to this game as the bounded budget betweenness centrality game and denote it as ?- B³C game, where ? is the path length constraint parameter.We present both complexity and constructive existence results about Nash equilibria of the game. For the nonuniform version of the game where node budgets, link costs, and pairwise communication weights may vary, we show that Nash equilibria may not exist and it is NP-hard to decide whether Nash equilibria exist in a game instance. For the uniform version of the game where link costs and pairwise communication weights are one and each node can build k links, we construct two families of Nash equilibria based on shift graphs, and study the properties of Nash equilibria. Moreover, we study the complexity of computing best responses and show that the task is polynomial for uniform 2- B³C games and NP-hard for other games (i.e. uniform ?- B³C games with ?≥3 and nonuniform ?- B³C games with ?≥2).     

基于动态贝叶斯博弈的攻击预测模型

提出了基于动态贝叶斯博弈的攻击预测模型。该模型能根据攻击者的历史行为，使用贝叶斯法则对网络中存在恶意主机节点的概率进行合理的修正，并以此为基础，通过分析攻击者和防御者双方的收益，预测出理性的攻击者和防御者在下一个博弈阶段会选择攻击和防御的概率。预测结果为网络安全管理员进行安全配置提供了有价值的参考依据，从而使被动的检测变为主动的有针对性的防御成为可能。最后介绍了相应的实验过程和结果分析，验证了模型的有效性。     

Representing von Neumann–Morgenstern Games in the Situation Calculus

Sequential von Neumann–Morgernstern (VM) games are a very general formalism for representing multi-agent interactions and planning problems in a variety of types of environments. We show that sequential VM games with countably many actions and continuous utility functions have a sound and complete axiomatization in the situation calculus. This axiomatization allows us to represent game-theoretic reasoning and solution concepts such as Nash equilibrium. We discuss the application of various concepts from VM game theory to the theory of planning and multi-agent interactions, such as representing concurrent actions and using the Baire topology to define continuous payoff functions.     

A reinforcement learning approach to fail-safe design for multiple space robots—cooperation mechanism without communication and negotiation schemes

This paper explores a fail-safe design for multiple space robots, which enables robots to complete given tasks even when they can no longer be controlled due to a communication accident or negotiation problem. As the first step towards this goal, we propose new reinforcement learning methods that help robots avoid deadlock situations in addition to improving the degree of task completion without communications via ground stations or negotiations with other robots. Through intensive simulations on a truss construction task, we found that our reinforcement learning methods have great potential to contribute towards fail-safe design for multiple space robots in the above case. Furthermore, the simulations revealed the following detailed implications: (i) the first several planned behaviors must not be reinforced with negative rewards even in deadlock situations in order to derive cooperation among multiple robots, (ii) a certain amount of positive rewards added into negative rewards in deadlock situations contributes to reducing the computational cost of finding behavior plans for task completion, and (iii) an appropriate balance between positive and negative rewards in deadlock situations is indispensable for finding good behavior plans at a small computational cost.     

Reliability maps for probabilistic guarantees of task motion for robotic manipulators

There are many applications for which reliable and safe robots are desired. For example, assistant robots for disabled or elderly people and surgical robots are required to be safe and reliable to prevent human injury and task failure. However, different levels of safety and reliability are required for different tasks so that understanding the reliability of robots is paramount. Currently, it is possible to guarantee the completion of a task when the robot is fault tolerant and the task remains in the fault-tolerant workspace (FTW). The traditional definition of FTW does not consider different reliabilities for the robotic manipulator's different joints. The aim of this paper is to extend the concept of a FTW to address the reliability of different joints. Such an extension can offer a wider FTW while maintaining the required level of reliability. This is achieved by associating a probability with every part of the workspace to extend the FTW. As a result, reliable fault-tolerant workspaces (RFTWs) are introduced by using the novel concept of conditional reliability maps. Such a RFTW can be used to improve the performance of assistant robots while providing the confidence that the robot remains reliable for completion of its assigned tasks.     

Pareto-optimal Nash equilibrium: Sufficient conditions and existence in mixed strategies

This paper considers the Nash equilibrium strategy profiles that are Pareto optimal with respect to the rest Nash equilibrium strategy profiles. The sufficient conditions for the existence of such pure strategy profiles are established. These conditions employ the Germeier convolutions of the payoff functions. For the non-cooperative games with compact strategy sets and continuous payoff functions, the existence of the Pareto optimal Nash equilibria in mixed strategies is proved.     

Game-theoretic analysis of an ancient Chinese horse race problem

This paper analyzes a legendary Chinese horse race problem involving the King of Qi and General Tianji which took place more than 2000 years ago. In this problem each player owns three horses of different speed classes and must choose the sequence of horses to compete against each other. Depending on the payoffs received by the players as a result of the horse races, we analyze two groups of constant-sum games. In each group, we consider three separate cases where the outcomes of the races are (i) deterministic, (ii) probabilistic within the same class, and (iii) probabilistic across classes. In the first group, the player who wins the majority of races receives a one-unit payoff. For this group we show analytically that the three different games with non-singular payoff matrices have the same solution where each player has a unique optimal mixed strategy with equal probabilities. For the second group of games where the payoff to a player is the total number of races his horses have won, we use linear programming with non-numeric data to show that the solution of the three games are mixed strategies given as a convex combination of two extreme points. We invoke results from information theory to prove that to maximize the opponent's “entropy” the players should use the equal probability mixed strategy that was found for the one-unit games.     

动态环境下多机器人合作追捕研究

主要研究了多个自主型移动机器人合作追捕多个运动猎物的追捕—逃避问题. 从基于范例的推理缩小任务招标范围、引入辅助决策矩阵改善联盟决策两个方面对传统的合同网协议进行了改进,以减少任务协商过程中的通信开销,接着引入了联盟生命值、违约金等概念,在此基础上,实现了一种允许动态联盟的多机器人合作追捕算法. 仿真实验证明了所提算法的可行性和有效性.     

Scalable and practical pursuit-evasion with networked robots

In this paper, we consider the design and implementation of practical pursuit-evasion games with networked robots, where a communication network provides sensing-at-a-distance as well as a communication backbone that enables tighter coordination between pursuers. We first develop, using the theory of zero-sum games, an algorithm that computes the minimal completion time strategy for pursuit-evasion when pursuers and evaders have same speed, and when all players make optimal decisions based on complete knowledge. Then, we extend this algorithm to when evader are significantly faster than pursuers. Unfortunately, these algorithms do not scale beyond a small number of robots. To overcome this problem, we design and implement a partition algorithm where pursuers capture evaders by decomposing the game into multiple multi-pursuer single-evader games. We show that the partition algorithm terminates, has bounded capture time, is robust, and is scalable in the number of robots. We then describe the design of a real-world mobile robot-based pursuit evasion game. We validate our algorithms by experiments in a moderate-scale testbed in a challenging office environment. Overall, our work illustrates an innovative interplay between robotics and communication.     

Antagonistic games with interval parameters

Antagonistic (matrix) games with payoff matrices given to within an interval are considered. The necessan and sufficient conditions of existence of solutions of such games are established. It is shown that the basic theorem of the Von Neumann theory is not valid for such games. The method of solution of an internal game by reducing it to two boundary exact games is proposed. Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 149–160, July–August, 1999.     

Equilibrium Trajectories in Dynamical Bimatrix Games with Average Integral Payoff Functionals

This paper considers models of evolutionary non-zero-sum games on the infinite time interval. Methods of differential game theory are used for the analysis of game interactions between two groups of participants. We assume that participants in these groups are controlled by signals for the behavior change. The payoffs of coalitions are defined as average integral functionals on the infinite horizon. We pose the design problem of a dynamical Nash equilibrium for the evolutionary game under consideration. The ideas and approaches of non-zero-sum differential games are employed for the determination of the Nash equilibrium solutions. The results derived in this paper involve the dynamic constructions and methods of evolutionary games. Much attention is focused on the formation of the dynamical Nash equilibrium with players strategies that maximize the corresponding payoff functions and have the guaranteed properties according to the minimax approach. An application of the minimax approach for constructing optimal control strategies generates dynamical Nash equilibrium trajectories yielding better results in comparison to static solutions and evolutionary models with the replicator dynamics. Finally, we make a comparison of the dynamical Nash equilibrium trajectories for evolutionary games with the average integral payoff functionals and the trajectories for evolutionary games with the global terminal payoff functionals on the infinite horizon.     

Synchronization Control for a Swarm of Unicycle Robots: Analysis of Different Controller Topologies

This paper proposes a nonlinear synchronization controller for a swarm of unicycle robots performing a cooperative task, i.e., following a desired trajectory per robot while maintaining a prescribed formation. The effect of communication between robots is analyzed and several network topologies are investigated, e.g., all‐to‐all, ring type, undirected, among others. The stability analysis of the closed loop system is provided using the Lyapunov method. Experiments with four unicycle robots are presented to validate the control law and communication analysis. Accumulated errors over the experiment time are presented in order to determine which topology is most efficient.     

基于双效用函数的无线传感器网络拓扑博弈算法

传统拓扑控制算法采用单个效用函数,无法适应网络性能需求的动态变化.在拓扑控制中引入了博弈论,提出了两个具有不同优化目标的效用函数.当节点剩余能量较高时,选择一个全面考虑能量均衡度、网络能耗、网络连通性等因素的效用函数;否则,为了尽可能降低节点能耗而选择另一个更趋向于较低功率的效用函数.实验表明,采用双效用函数的拓扑博弈算法在网络寿命、能量均衡度等方面具有较好的性能.     

Contribution Games in Networks

We consider network contribution games, where each agent in a network has a budget of effort that he can contribute to different collaborative projects or relationships. Depending on the contribution of the involved agents a relationship will flourish or drown, and to measure the success we use a reward function for each relationship. Every agent is trying to maximize the reward from all relationships that it is involved in. We consider pairwise equilibria of this game, and characterize the existence, computational complexity, and quality of equilibrium based on the types of reward functions involved. When all reward functions are concave, we prove that the price of anarchy is at most?2. For convex functions the same only holds under some special but very natural conditions. Another special case extensively treated are minimum effort games, where the reward of a relationship depends only on the minimum effort of any of the participants. In these games, we can show existence of pairwise equilibrium and a price of anarchy of 2 for concave functions and special classes of games with convex functions. Finally, we show tight bounds for approximate equilibria and convergence of dynamics in these games.     

Hierarchical multi-agent planning for flexible assembly of large-scale lunar facilities

Several national space agencies and commercial aerospace companies plan to set up lunar bases with large-scale facilities that rely on multiple lunar robots’ assembly. Mission planning is necessary to achieve efficient multi-robot cooperation. This paper aims at autonomous multi-robot planning for the flexible assembly of the large-scale lunar facility, considering the harsh lunar environment, mission time optimization, and joint actions. The lunar robots and modules are scattered around the mission area without fixed assembly lines. Thus, the traditional assembly planning methods ignoring the optimal selection of modules are unable to handle this problem. We propose a hierarchical multi-agent planning method based on two-stage two-sided matching (HMAP-TTM) to solve this critical problem. First, the distributed planning framework with multi-replica public agents is introduced, ensuring robot plan knowledge consistency through public agents’ communication. Second, the hierarchical task graph (HTG) divides the mission into task layers based on task dependency knowledge. Third, we develop a novel two-stage two-sided matching algorithm. Time-optimal plans emerge from the matching games among public and private agents in each layer of HTG. Agents make decisions in the game based on action knowledge updated during planning. Finally, an assembly mission is presented to prove the method’s effectiveness. The simulation results show that the HMAP-TTM can generate plans with shorter mission time and require smaller communication costs than the baseline methods.     

Project-oriented task scheduling for mobile robot team

This paper presents a project-oriented framework for multi-robot task scheduling. An agent-based architecture is designed to schedule tasks where robots are considered as resources. The study focused on the problems when the number of available robots is less than the required number. In this case, the problem becomes a resource-constrained scheduling problem. Initially, tasks are scheduled by using Critical path method (CPM), resource leveling method is used to smooth the deviation between the resource requirements and available resource levels, and tasks are allocated to robots. As robots perform their tasks, a monitoring agent observes them and tasks are rescheduled if the difference between the planned and actual completion time of tasks exceeds a predefined threshold. Effectiveness of the proposed approach is shown by using a nine-task two-robot project simulation.     

Convergence Analysis for Symmetric Arbitration Games FOA and DOA

Up to now, results on the existence of Nash equilibrium have required either continuity of payoff functions or compactness of strategy sets. However, in the arbitration games FOA and DOA, neither condition is satisfied. This paper first gives a new existence result for a general game. The result is then applied to the symmetric arbitration games FOA and DOA. The conclusions of this paper generalize the main result of Zeng, Nakamura and Ibaraki (1996), that DOA leads to a convergence of offers but FOA does not.     

A PLANNING APPROACH TO DECLARER PLAY IN CONTRACT BRIDGE

Although game-tree search works well in perfect-information games, it is less suitable for imperfect-information games such as contract bridge. The lack of knowledge about the opponents' possible moves gives the game tree a very large branching factor, making it impossible to search a significant portion of this tree in a reasonable amount of time.
This paper describes our approach for overcoming this problem. We represent information about bridge in a task network extended to represent multi-agency and uncertainty. Our game-playing procedure uses this task network to generate game trees in which the set of alternative choices is determined not by the set of possible actions, but by the set of available tactical and strategic schemes.
We have tested this approach on declarer play in the game of bridge, in an implementation called Tignum 2. On 5000 randomly generated notrump deals, Tignum 2 beat the strongest commercially available program by 1394 to 1302, with 2304 ties. These results are statistically significant at the α= 0.05 level. Tignum 2 searched an average of only 8745.6 moves per deal in an average time of only 27.5 seconds per deal on a Sun SPARCstation 10. Further enhancements to Tignum 2 are currently underway.