Positional Consensus of Multi-Agent Systems Using Linear Programming Based Decentralized Control with Rectilinear Decision Domain

In this paper we develop a Linear Programming (LP) based decentralized algorithm for a group of multiple autonomous agents to achieve positional consensus. Each agent is capable of exchanging information about its position and orientation with other agents within their sensing region. The method is computationally feasible and easy to implement. Analytical results are presented. The effectiveness of the approach is illustrated with simulation results.

Automated Multi-Agent Search Using Centroidal Voronoi Configuration

This paper addresses the problem of automated multiagent search in an unknown environment. Autonomous agents equipped with sensors carry out a search operation in a search space, where the uncertainty, or lack of information about the environment, is known a priori as an uncertainty density distribution function. The agents are deployed in the search space to maximize single step search effectiveness. The centroidal Voronoi configuration, which achieves a locally optimal deployment, forms the basis for the proposed sequential deploy and search strategy. It is shown that with the proposed control law the agent trajectories converge in a globally asymptotic manner to the centroidal Voronoi configuration. Simulation experiments are provided to validate the strategy. Note to Practitioners-In this paper, searching an unknown region to gather information about it is modeled as a problem of using search as a means of reducing information uncertainty about the region. Moreover, multiple automated searchers or agents are used to carry out this operation optimally. This problem has many applications in search and surveillance operations using several autonomous UAVs or mobile robots. The concept of agents converging to the centroid of their Voronoi cells, weighted with the uncertainty density, is used to design a search strategy named as sequential deploy and search. Finally, the performance of the strategy is validated using simulations.

The precision of regulation in Dictyostelium discoideum: implications for cell-type proportioning in the absence of spatial pattern

We have made careful counts of the exact number of spore, stalk and basal disc cells in small fruiting bodies of Dictyostelium discoideum (undifferentiated amoebae are found only rarely and on average their fraction is 4.96 x 10(-4)). (i) Within aggregates of a given size, the relative apportioning of amoebae to the main cell types occurs with a remarkable degree of precision. In most cases the coefficient of variation (c.v.) in the mean fraction of cells that form spores is within 4.86%. The contribution of stalk and basal disc cells is highly variable when considered separately (c.v.'s upto 25% and 100%, respectively), but markedly less so when considered together. Calculations based on theoretical models indicate that purely cell-autonomous specification of cell, fate cannot account for die observed accuracy of proportioning. Cell-autonomous determination to a prestalk or prespore condition followed by cell type interconversion, and stabilised by feedbacks, suffices to explain the measured accuracy. (ii) The fraction of amoebae that differentiates into spores increases monotonically with the total number of cells. This fraction rises from an average of 73.6% for total cell numbers below 30 and reaches 86.0% for cell numbers between 170 and 200 (it remains steady thereafter at around 86%). Correspondingly, the fraction of amoebae differentiating into stalk or basal disc decreases viith total size. These trends are in accordance with evolutionary expectations and imply that a mechanism for sensing the overall size of the aggregate also plays an essential role in the determination of cell-type proportions.

Optimal control of a stochastic hybrid system with discounted cost

We address the optimal control problem of a very general stochastic hybrid system with both autonomous and impulsive jumps. The planning horizon is infinite and we use the discounted-cost criterion for performance evaluation. Under certain assumptions, we show the existence of an optimal control. We then derive the quasivariational inequalities satisfied by the value function and establish well-posedness. Finally, we prove the usual verification theorem of dynamic programming.

Population genetic structure and conservation of Asian elephants (Elephas maximus) across India

This study examines the population genetic structure of Asian elephants (Elephas maximus) across India, which harbours over half the world's population of this endangered species. Mitochondrial DNA control region sequences and allele frequencies at six nuclear DNA microsatellite markers obtained from the dung of free-ranging elephants reveal low mtDNA and typical microsatellite diversity. Both known divergent clades of mtDNA haplotypes in the Asian elephant are present in India, with southern and central India exhibiting exclusively the β clade of Fernando et al. (2000), northern India exhibiting exclusively the α clade and northeastern India exhibiting both, but predominantly the α clade. A nested clade analysis revealed isolation by distance as the principal mechanism responsible for the observed haplotype distributions within the α and β clades. Analyses of molecular variance and pairwise population FST tests based on both mitochondrial and microsatellite DNA suggest that northern-northeastern India, central India, Nilgiris (in southern India) and Anamalai-Periyar (in southern India) are four demographically autonomous population units and should be managed separately. In addition, evidence for female philopatry, male-mediated gene flow and two possible historical biogeographical barriers is described.

Determining Top K Nodes in Social Networks using the Shapley Value

In this paper, we consider the problem of selecting, for any given positive integer k, the top-k nodes in a social network, based on a certain measure appropriate for the social network. This problem is relevant in many settings such as analysis of co-authorship networks, diffusion of information, viral marketing, etc. However, in most situations, this problem turns out to be NP-hard. The existing approaches for solving this problem are based on approximation algorithms and assume that the objective function is sub-modular. In this paper, we propose a novel and intuitive algorithm based on the Shapley value, for efficiently computing an approximate solution to this problem. Our proposed algorithm does not use the sub-modularity of the underlying objective function and hence it is a general approach. We demonstrate the efficacy of the algorithm using a co-authorship data set from e-print arXiv (www.arxiv.org), having 8361 authors.

Multi-agent search using?sensors with heterogeneous capabilities

In this thesis we address the problem of multi-agent search. We formulate two deploy and search strategies based on optimal deployment of agents in search space so as to maximize the search effectiveness in a single step. We show that a variation of centroidal Voronoi configuration is the optimal deployment. When the agents have sensors with different capabilities, the problem will be heterogeneous in nature. We introduce a new concept namely, generalized Voronoi partition in order to formulate and solve the heterogeneous multi-agent search problem. We address a few theoretical issues such as optimality of deployment, convergence and spatial distributedness of the control law and the search strategies. Simulation experiments are carried out to compare performances of the proposed strategies with a few simple search strategies.

Community-based Natural Resource Management: Issues and Cases from South Asia

Community-based natural resource management (CBNRM) is the joint management of natural resources by a community based on a community strategy, through a participatory mechanism involving all legitimate stakeholders. The approach is community-based in that the communities managing the resources have the legal rights, the local institutions and the economic incentives to take substantial responsibility for sustained use of these resources. This implies that the community plays an active role in the management of natural resources, not because it asserts sole ownership over them, but because it can claim participation in their management and benefits for practical and technical reasons1–4. This approach emerged as the dominant conservation concept in the late 1970s and early 1980s, of the disillusionment with the developmental state. Governments across South and South East Asia, Africa and Latin America have adopted and implemented CBNRM in various ways, viz. through sectoral programmes such as forestry, irrigation or wildlife management, multisectoral programmes such as watershed development and efforts towards political devolution. In India, the principle of decentralization through ‘gram swaraj’ was introduced by Mahatma Gandhi. The 73rd and 74th constitution amendments in 1992 gave impetus to the decentralized planning at panchayat levels through the creation of a statutory three-level local self-government structure5,6. The strength of this book is that it includes chapters by CBNRM advocates based on six seemingly innovative initiatives being implemented by nongovernmental organizations (NGOs) in ecologically vulnerable regions of South Asia: two in the Himalayas (watershed development programme in Lingmutechhu, Bhuthan and Thalisain tehsil, Paudi Grahwal District, Uttarakhand), three in semi-arid parts of western India (watershed development in Hivre Bazar, Maharashtra and Nathugadh village, Gujarat and water-harvesting structures in Gopalapura, Rajasthan) and one in the flood-plains of the Brahmaputra–Jamuna (Char land, Galibanda and Jamalpur districts, Bangladesh). Watersheds in semi-arid regions fall in the low-rainfall region (500–700 mm) and suffer the vagaries of drought 2–3 years in every five-year cycle. In all these locations, the major occupation is agriculture, most of which is rainfed or dry. The other two cases (in Uttarakhand) fall in the Himalayan region (temperate/sub-temperate climate), which has witnessed extensive deforestation in the last century and is now considered as one of the most vulnerable locations in South Asia. Terraced agriculture is being practised in these locations for a long time. The last case (Gono Chetona) falls in the Brahmaputra–Jamuna charlands which are the most ecologically vulnerable regions in the sub-continent with constantly changing landscape. Agriculture and livestock rearing are the main occupations, and there is substantial seasonal emigration for wage labour by the adult males. River erosion and floods force the people to adopt a semi-migratory lifestyle. The book attempts to analyse the potential as well as limitations of NGOdriven CBNRM endeavours across agroclimatic regions of South Asia with emphasis on four intrinsically linked normative concerns, namely sustainability, livelihood enhancement, equity and demographic decentralization in chapters 2–7. Comparative analysis of these case studies done in chapter 8, highlights the issues that require further research while portraying the strengths and limits of NGO-driven CBNRM. In Hivre Bazar, the post-watershed intervention scenario is such that farmers often grow three crops in a year – kharif bajra, rabi jowar and summer vegetable crops. Productivity has increased in the dry lands due to improvement in soil moisture levels. The revival of johads in Gopalpura has led to the proliferation of wheat and increased productivity. In Lingmuteychhu, productivity gains have also arisen, but more due to the introduction of both local and high-yielding, new varieties as opposed to increased water availability. In the case of Gono Chetona, improvements have come due to diversification of agriculture; for example, the promotion of vegetable gardens. CBNRM interventions in most cases have also led to new avenues of employment and income generation. The synthesis shows that CBNRM efforts have made significant contributions to livelihood enhancement and only limited gains in terms of collective action for sustainable and equitable access to benefits and continuing resource use, and in terms of democratic decentralization, contrary to the objectives of the programme. Livelihood benefits include improvements in availability of livelihood support resources (fuelwood, fodder, drinking water), increased productivity (including diversification of cropping pattern) in agriculture and allied activities, and new sources of livelihood. However, NGO-driven CBNRM has not met its goal of providing ‘alternative’ forms of ‘development’ due to impediments of state policy, short-sighted vision of implementers and confrontation with the socio-ecological reality of the region, which almost always are that of fragmented communities (or communities in flux) with unequal dependence and access to land and other natural resources along with great gender imbalances. Appalling, however, is the general absence of recognition of the importance of and the will to explore practical ways to bring about equitable resource transfer or benefit-sharing and the consequent innovations in this respect that are evident in the pioneering community initiatives such as pani panchayat, etc. Pertaining to the gains on the ecological sustainability front, Hivre Bazar and Thalisain initiatives through active participation of villagers have made significant regeneration of the water table within the village, and mechanisms such as ban on number of bore wells, the regulation of cropping pattern, restrictions on felling of trees and free grazing to ensure that in the future, the groundwater is neither over-exploited nor its recharge capability impaired. Nevertheless, the longterm sustainability of the interventions in the case of Ghoga and Gopalpura initiatives as the focus has been mostly on regeneration of resources, and less on regulating the use of regenerated resources. Further, in Lingmuteychhu and Gono Chetona, the interventions are mainly household-based and the focus has been less explicit on ecological components. The studies demonstrate the livelihood benefits to all of the interventions and significant variation in achievements with reference to sustainability, equity and democratic decentralization depending on the level and extent of community participation apart from the vision of implementers, strategy (or nature of intervention shaped by the question of community formation), the centrality of community formation and also the State policy. Case studies show that the influence of State policy is multi-faceted and often contradictory in nature. This necessitates NGOs to engage with the State in a much more purposeful way than in an ‘autonomous space’. Thus the role of NGOs in CBNRM is complementary, wherein they provide innovative experiments that the State can learn. This helps in achieving the goals of CBNRM through democratic decentralization. The book addresses the vital issues related to natural resource management and interests of the community. Key topics discussed throughout the book are still at the centre of the current debate. This compilation consists of well-written chapters based on rigorous synthesis of CBNRM case studies, which will serve as good references for students, researchers and practitioners in the years to come.

Multi-agent Search using Voronoi partitions

This paper addresses the problem of multiagent search in an unknown environment. The agents are autonomous in nature and are equipped with necessary sensors to carry out the search operation. The uncertainty, or lack of information about the search area is known a priori as a probability density function. The agents are deployed in an optimal way so as to maximize the one step uncertainty reduction. The agents continue to deploy themselves and reduce uncertainty till the uncertainty density is reduced over the search space below a minimum acceptable level. It has been shown, using LaSalle’s invariance principle, that a distributed control law which moves each of the agents towards the centroid of its Voronoi partition, modified by the sensor range leads to single step optimal deployment. This principle is now used to devise search trajectories for the agents. The simulations were carried out in 2D space with saturation on speeds of the agents. The results show that the control strategy per step indeed moves the agents to the respective centroid and the algorithm reduces the uncertainty distribution to the required level within a few steps.

Generalization of the collision cone approach for motion safety in 3-D environments

Avoidance of collision between moving objects in a 3-D environment is fundamental to the problem of planning safe trajectories in dynamic environments. This problem appears in several diverse fields including robotics, air vehicles, underwater vehicles and computer animation. Most of the existing literature on collision prediction assumes objects to be modelled as spheres. While the conservative spherical bounding box is valid in many cases, in many other cases, where objects operate in close proximity, a less conservative approach, that allows objects to be modelled using analytic surfaces that closely mimic the shape of the object, is more desirable. In this paper, a collision cone approach (previously developed only for objects moving on a plane) is used to determine collision between objects, moving in 3-D space, whose shapes can be modelled by general quadric surfaces. Exact collision conditions for such quadric surfaces are obtained and used to derive dynamic inversion based avoidance strategies.

Performance of a class of multi-robot deploy and search strategies based on centroidal voronoi configurations

This article considers a class of deploy and search strategies for multi-robot systems and evaluates their performance. The application framework used is deployment of a system of autonomous mobile robots equipped with required sensors in a search space to gather information. The lack of information about the search space is modelled as an uncertainty density distribution. The agents are deployed to maximise single-step search effectiveness. The centroidal Voronoi configuration, which achieves a locally optimal deployment, forms the basis for sequential deploy and search (SDS) and combined deploy and search (CDS) strategies. Completeness results are provided for both search strategies. The deployment strategy is analysed in the presence of constraints on robot speed and limit on sensor range for the convergence of trajectories with corresponding control laws responsible for the motion of robots. SDS and CDS strategies are compared with standard greedy and random search strategies on the basis of time taken to achieve reduction in the uncertainty density below a desired level. The simulation experiments reveal several important issues related to the dependence of the relative performances of the search strategies on parameters such as the number of robots, speed of robots and their sensor range limits.

Incentive Compatible Influence Maximization in Social Networks with Application to Viral Marketing

Information diffusion and influence maximization are important and extensively studied problems in social networks. Various models and algorithms have been proposed in the literature in the context of the influence maximization problem. A crucial assumption in all these studies is that the influence probabilities are known to the social planner. This assumption is unrealistic since the influence probabilities are usually private information of the individual agents and strategic agents may not reveal them truthfully. Moreover, the influence probabilities could vary significantly with the type of the information flowing in the network and the time at which the information is propagating in the network. In this paper, we use a mechanism design approach to elicit influence probabilities truthfully from the agents. Our main contribution is to design a scoring rule based mechanism in the context of the influencer-influencee model. In particular, we show the incentive compatibility of the mechanisms and propose a reverse weighted scoring rule based mechanism as an appropriate mechanism to use.

A strategy-proof and budget-balanced mechanism for carbon footprint reduction by global companies

The problem addressed in this paper is concerned with an important issue faced by any green aware global company to keep its emissions within a prescribed cap. The specific problem is to allocate carbon reductions to its different divisions and supply chain partners in achieving a required target of reductions in its carbon reduction program. The problem becomes a challenging one since the divisions and supply chain partners, being autonomous, may exhibit strategic behavior. We use a standard mechanism design approach to solve this problem. While designing a mechanism for the emission reduction allocation problem, the key properties that need to be satisfied are dominant strategy incentive compatibility (DSIC) (also called strategy-proofness), strict budget balance (SBB), and allocative efficiency (AE). Mechanism design theory has shown that it is not possible to achieve the above three properties simultaneously. In the literature, a mechanism that satisfies DSIC and AE has recently been proposed in this context, keeping the budget imbalance minimal. Motivated by the observation that SBB is an important requirement, in this paper, we propose a mechanism that satisfies DSIC and SBB with slight compromise in allocative efficiency. Our experimentation with a stylized case study shows that the proposed mechanism performs satisfactorily and provides an attractive alternative mechanism for carbon footprint reduction by global companies.

Optimal incentive timing strategies for product marketing on social networks

We consider the problem of devising incentive strategies for viral marketing of a product. In particular, we assume that the seller can influence penetration of the product by offering two incentive programs: a) direct incentives to potential buyers (influence) and b) referral rewards for customers who influence potential buyers to make the purchase (exploit connections). The problem is to determine the optimal timing of these programs over a finite time horizon. In contrast to algorithmic perspective popular in the literature, we take a mean-field approach and formulate the problem as a continuous-time deterministic optimal control problem. We show that the optimal strategy for the seller has a simple structure and can take both forms, namely, influence-and-exploit and exploit-and-influence. We also show that in some cases it may optimal for the seller to deploy incentive programs mostly for low degree nodes. We support our theoretical results through numerical studies and provide practical insights by analyzing various scenarios.