Toward better approximation for the minimum-weighted vertex cover (MWVC) problem in multiagent systems, we present a distributed algorithm from the perspective of learning in games. For self-organized coordination and optimization, we see each vertex as a potential game player who makes decisions using local information of its own and the immediate neighbors. The resulting Nash equilibrium is classified into two categories, i.e., the inferior Nash equilibrium (INE) and the dominant Nash equilibrium (DNE). We show that the optimal solution must be a DNE. To achieve better approximation ratios, local rules of perturbation and weighted memory are designed, with the former destroying the stability of an INE and the latter facilitating the refinement of a DNE. By showing the existence of an improvement path from any INE to a DNE, we prove that when the memory length is larger than 1, our algorithm converges in finite time to DNEs, which could not be improved by exchanging the action of a selected node with all its unselected neighbors. Moreover, additional freedom for solution efficiency refinement is provided by increasing the memory length. Finally, intensive comparison experiments demonstrate the superiority of the presented methodology to the state of the art, both in solution efficiency and computation speed.

Area coverage and network lifetime are two contradictory issues to the architecture development of a wireless sensor network (WSN). A satisfactory balance could be achieved by deploying abundant sensor nodes randomly and dividing them into$k$exclusive cover sets. Toward self-organized partition with higher efficiency, we address the problem from the perspective of networked potential games and propose a memorial mixed-response algorithm (MMRA), which is implemented in a distributed and synchronous manner. Being viewed as a game player, each sensor node first updates its memory using a temporary action, which is generated by following a mixed response rule. After this, the coordination evolves into the next iteration by each player randomly drawing an action from its memory with equal probabilities. We prove that our algorithm converges with probability 1 to a convention of Nash equilibria, with the worst approximation ratio strictly larger than 0.5. Moreover, it is also found that a tradeoff between solution efficiency and computation time could be achieved via the adjustment of the amount of randomness introduced via the memory length$m$as well as the probability$p_{m}$, where better partition results are more likely to be generated using a larger$m$and smaller$p_{m}$. Comparisons with existing distributed methods demonstrate the superiority of our method in terms of solution refinement as well as convergence speed.

Toward the global optimality and computation time reduction, we address the minimum weighted vertex cover (MWVC) problem by proposing a population based game theoretic optimizer (PGTO) that combines learning in games with population based optimization. A population of candidate solutions are iterated through the procedures of swarm evolution (SE), learning in games (LIG), and local search (LS). Via strict theoretic analysis, we prove that LIG converges with probability one to Nash equilibria which could be further refined by LS. Numerical simulations show that a larger population size and a proper mutation probability are more likely to provide the best performance. Comparison experiments with typical algorithms demonstrate the superiority of the presented methodology to the state of the art, both in terms of solution efficiency and computation time.

Toward the minimal weighted vertex cover (MWVC) in agent-based networking systems, this paper recasts it as a potential game and proposes a distributed learning algorithm based on relaxed greed and finite memory. With the concept of convention, we prove that our algorithm converges with probability 1 to Nash equilibria, which serve as the bridge connecting the game and the MWVC. More importantly, an additional degree of freedom is also provided for equilibrium refinement, such that increasing memory lengths and mutation probabilities contributes to the improvement of system-level objectives. Comparisons with typical methods, centralized and distributed, demonstrate the advantage of our algorithm for both weighted and unweighted versions. This paper not only provides a useful tool for the MWVC problem in decentralized environments but also paves an effective way for distributed coordination and optimization that could be modeled as potential games.

Mission planning for a cluster of earth observing satellites is a complex problem that raises significant theoretical and technological challenges, especially in distributed environments. Towards efficient cooperation relying on local information only, we cast the problem into a networked potential game by viewing each satellite as a rational player and propose a distributed coordination and optimization algorithm. By each player interacting with the neighbors and adapting the local plan following a restricted greed and memory based rule, stable Nash equilibria are proven to emerge with probability 1. Moreover, with the increase of randomness introduced by a longer memory, a refined Nash equilibrium can also be guaranteed, which corresponds to closer cooperation among individual satellites and better system-level performance. Comparison experiments with typical methods, centralized and distributed, highlight the advantages of the presented methodology.

Sensor location is important to sensor networks since many cooperative tasks depend on it. Focusing on the lost-in-space localization problem without prior location knowledge, this paper describes a self-organized and fully distributed algorithm where nodes start from a random guessed coordinate assignment and converge to a consistent solution with actual locations using ranging measurements and neighboring interaction only. It is most likely for this algorithm to overcome local minima and result in the global optimum by introducing an improved interacting mechanism where nodes interact according to a simulated switching computational topology. Numerical simulations demonstrate the effectiveness and robustness of the algorithm.

This paper focuses on recognizing the correct match of star identification among multiple possible candidates for star trackers. Derived from the perturbation theory, a tolerance criterion is proposed and proved to check the correctness of the candidates. A recognition algorithm is then proposed based on the tolerance criterion to select the correct match. Compared to traditional recognition algorithms, the proposed algorithm provides a straightforward and deterministic procedure and avoids non-deterministic, time-consuming, inefficient lookingup operations. Finally, simulation examples are given to show processing details and verify the proposed algorithm.