Negotiation schemes for multi-agent cooperative search

Because of limited sensor and communication ranges, designing efficient mechanisms for cooperative tasks is difficult. In this article, several negotiation schemes for multiple agents performing a cooperative task are presented. The negotiation schemes provide suboptimal solutions, but have attractive features of fast decision-making, and scalability to large number of agents without increasing the complexity of the algorithm. A software agent architecture of the decision-making process is also presented. The effect of the magnitude of information flow during the negotiation process is studied by using different models of the negotiation scheme. The performance of the various negotiation schemes, using different information structures, is studied based on the uncertainty reduction achieved for a specified number of search steps. The negotiation schemes perform comparable to that of optimal strategy in terms of uncertainty reduction and also require very low computational time, similar to 7 per cent to that of optimal strategy. Finally, analysis on computational and communication requirement for the negotiation schemes is carried out.

Two-agent cooperative search using game models with endurance-time constraints

In this article, the problem of two Unmanned Aerial Vehicles (UAVs) cooperatively searching an unknown region is addressed. The search region is discretized into hexagonal cells and each cell is assumed to possess an uncertainty value. The UAVs have to cooperatively search these cells taking limited endurance, sensor and communication range constraints into account. Due to limited endurance, the UAVs need to return to the base station for refuelling and also need to select a base station when multiple base stations are present. This article proposes a route planning algorithm that takes endurance time constraints into account and uses game theoretical strategies to reduce the uncertainty. The route planning algorithm selects only those cells that ensure the agent will return to any one of the available bases. A set of paths are formed using these cells which the game theoretical strategies use to select a path that yields maximum uncertainty reduction. We explore non-cooperative Nash, cooperative and security strategies from game theory to enhance the search effectiveness. Monte-Carlo simulations are carried out which show the superiority of the game theoretical strategies over greedy strategy for different look ahead step length paths. Within the game theoretical strategies, non-cooperative Nash and cooperative strategy perform similarly in an ideal case, but Nash strategy performs better than the cooperative strategy when the perceived information is different. We also propose a heuristic based on partitioning of the search space into sectors to reduce computational overhead without performance degradation.

Self assessment schemes for multi-agent cooperative search

In this paper, we present self assessment schemes (SAS) for multiple agents performing a search mission on an unknown terrain. The agents are subjected to limited communication and sensor ranges. The agents communicate and coordinate with their neighbours to arrive at route decisions. The self assessment schemes proposed here have very low communication and computational overhead. The SAS also has attractive features like scalability to large number of agents and fast decision-making capability. SAS can be used with partial or complete information sharing schemes during the search mission. We validate the performance of SAS using simulation on a large search space consisting of 100 agents with different information structures and self assessment schemes. We also compare the results obtained using SAS with that of a previously proposed negotiation scheme. The simulation results show that the SAS is scalable to large number of agents and can perform as good as the negotiation schemes with reduced communication requirement (almost 20% of that required for negotiation).

Self Assessment-Based Decision Making for Multiagent Cooperative Search

This paper addresses a search problem with multiple limited capability search agents in a partially connected dynamical networked environment under different information structures. A self assessment-based decision-making scheme for multiple agents is proposed that uses a modified negotiation scheme with low communication overheads. The scheme has attractive features of fast decision-making and scalability to large number of agents without increasing the complexity of the algorithm. Two models of the self assessment schemes are developed to study the effect of increase in information exchange during decision-making. Some analytical results on the maximum number of self assessment cycles, effect of increasing communication range, completeness of the algorithm, lower bound and upper bound on the search time are also obtained. The performance of the various self assessment schemes in terms of total uncertainty reduction in the search region, using different information structures is studied. It is shown that the communication requirement for self assessment scheme is almost half of the negotiation schemes and its performance is close to the optimal solution. Comparisons with different sequential search schemes are also carried out. Note to Practitioners-In the futuristic military and civilian applications such as search and rescue, surveillance, patrol, oil spill, etc., a swarm of UAVs can be deployed to carry out the mission for information collection. These UAVs have limited sensor and communication ranges. In order to enhance the performance of the mission and to complete the mission quickly, cooperation between UAVs is important. Designing cooperative search strategies for multiple UAVs with these constraints is a difficult task. Apart from this, another requirement in the hostile territory is to minimize communication while making decisions. This adds further complexity to the decision-making algorithms. In this paper, a self-assessment-based decision-making scheme, for multiple UAVs performing a search mission, is proposed. The agents make their decisions based on the information acquired through their sensors and by cooperation with neighbors. The complexity of the decision-making scheme is very low. It can arrive at decisions fast with low communication overheads, while accommodating various information structures used for increasing the fidelity of the uncertainty maps. Theoretical results proving completeness of the algorithm and the lower and upper bounds on the search time are also provided.

Approches générales de résolution pour les problèmes multi-attributs de tournées de véhicules et confection d'horaires

Thèse réalisée en cotutelle entre l'Université de Montréal et l'Université de Technologie de Troyes

La concepción aristotélica de la filosofía como una búsqueda cooperativa de la verdad

En el fragmento 5 del Protréptico, Aristóteles describe la filosofía como un tipo de investigación cuyo objetivo es la adquisición de la sabiduría, esto es, de la phrónesis. Paralelamente, en el segundo libro de la Metafísica, al hablar sobre la facilidad o dificultad de la investigación sobre la verdad, Aristóteles menciona el valor del aporte de sus predecesores. Allí, Aristóteles enfatiza que aun aquellos que han estudiado superficialmente la naturaleza de las cosas han hecho una contribución en esa búsqueda (II 1, 993b, 11-15). La lectura de este libro de la Metafísica a la luz de los fragmentos del Protréptico nos induce a pensar que Aristóteles concibe la filosofía como un quehacer cooperativo en el cual participa, de alguna manera, toda la tradición filosófica. Dado esto, el objetivo de este trabajo es indagar esta concepción de la filosofía, centrándonos principalmente en los fragmentos citados del Protréptico y el segundo libro de la Metafísica

La crítica como búsqueda cooperativa de la verdad : El argumento del tercer hombre en el Sobre las Ideas de Aristóteles

La versión más precisa del argumento "del tercer hombre" es la proporcionada por Aristóteles en el tratado Sobre las ideas. En este trabajo ofreceré, en primer lugar, un análisis del argumento, estableciendo sus presupuestos que lo tornan una crítica válida. En segundo lugar, me detendré en la posible respuesta platónica a la objeción con el propósito de mostrar que Aristóteles descubre una dificultad genuina en la posición platónica: la separación entre Ideas y particulares conlleva el problema de la homonimia. Creemos que una reflexión profunda en torno al argumento condujo a Aristóteles a establecer la importante distinción entre predicación esencial y predicación accidental así como a sostener que existe una relación de sinonimia entre el sujeto y su esencia. En tal sentido, el examen de este argumento ilustra el modo en que para Aristóteles la crítica es un procedimiento válido y habitual en la búsqueda cooperativa de la verdad

La concepción aristotélica de la filosofía como una búsqueda cooperativa de la verdad

En el fragmento 5 del Protréptico, Aristóteles describe la filosofía como un tipo de investigación cuyo objetivo es la adquisición de la sabiduría, esto es, de la phrónesis. Paralelamente, en el segundo libro de la Metafísica, al hablar sobre la facilidad o dificultad de la investigación sobre la verdad, Aristóteles menciona el valor del aporte de sus predecesores. Allí, Aristóteles enfatiza que aun aquellos que han estudiado superficialmente la naturaleza de las cosas han hecho una contribución en esa búsqueda (II 1, 993b, 11-15). La lectura de este libro de la Metafísica a la luz de los fragmentos del Protréptico nos induce a pensar que Aristóteles concibe la filosofía como un quehacer cooperativo en el cual participa, de alguna manera, toda la tradición filosófica. Dado esto, el objetivo de este trabajo es indagar esta concepción de la filosofía, centrándonos principalmente en los fragmentos citados del Protréptico y el segundo libro de la Metafísica

La crítica como búsqueda cooperativa de la verdad : El argumento del tercer hombre en el Sobre las Ideas de Aristóteles

La versión más precisa del argumento "del tercer hombre" es la proporcionada por Aristóteles en el tratado Sobre las ideas. En este trabajo ofreceré, en primer lugar, un análisis del argumento, estableciendo sus presupuestos que lo tornan una crítica válida. En segundo lugar, me detendré en la posible respuesta platónica a la objeción con el propósito de mostrar que Aristóteles descubre una dificultad genuina en la posición platónica: la separación entre Ideas y particulares conlleva el problema de la homonimia. Creemos que una reflexión profunda en torno al argumento condujo a Aristóteles a establecer la importante distinción entre predicación esencial y predicación accidental así como a sostener que existe una relación de sinonimia entre el sujeto y su esencia. En tal sentido, el examen de este argumento ilustra el modo en que para Aristóteles la crítica es un procedimiento válido y habitual en la búsqueda cooperativa de la verdad

La concepción aristotélica de la filosofía como una búsqueda cooperativa de la verdad

En el fragmento 5 del Protréptico, Aristóteles describe la filosofía como un tipo de investigación cuyo objetivo es la adquisición de la sabiduría, esto es, de la phrónesis. Paralelamente, en el segundo libro de la Metafísica, al hablar sobre la facilidad o dificultad de la investigación sobre la verdad, Aristóteles menciona el valor del aporte de sus predecesores. Allí, Aristóteles enfatiza que aun aquellos que han estudiado superficialmente la naturaleza de las cosas han hecho una contribución en esa búsqueda (II 1, 993b, 11-15). La lectura de este libro de la Metafísica a la luz de los fragmentos del Protréptico nos induce a pensar que Aristóteles concibe la filosofía como un quehacer cooperativo en el cual participa, de alguna manera, toda la tradición filosófica. Dado esto, el objetivo de este trabajo es indagar esta concepción de la filosofía, centrándonos principalmente en los fragmentos citados del Protréptico y el segundo libro de la Metafísica

La crítica como búsqueda cooperativa de la verdad : El argumento del tercer hombre en el Sobre las Ideas de Aristóteles

La versión más precisa del argumento "del tercer hombre" es la proporcionada por Aristóteles en el tratado Sobre las ideas. En este trabajo ofreceré, en primer lugar, un análisis del argumento, estableciendo sus presupuestos que lo tornan una crítica válida. En segundo lugar, me detendré en la posible respuesta platónica a la objeción con el propósito de mostrar que Aristóteles descubre una dificultad genuina en la posición platónica: la separación entre Ideas y particulares conlleva el problema de la homonimia. Creemos que una reflexión profunda en torno al argumento condujo a Aristóteles a establecer la importante distinción entre predicación esencial y predicación accidental así como a sostener que existe una relación de sinonimia entre el sujeto y su esencia. En tal sentido, el examen de este argumento ilustra el modo en que para Aristóteles la crítica es un procedimiento válido y habitual en la búsqueda cooperativa de la verdad

Basic ingredients for mathematical modeling of tumor growth in vitro: Cooperative effects and search for space

Based on the literature data from HT-29 cell monolayers, we develop a model for its growth, analogous to an epidemic model, mixing local and global interactions. First, we propose and solve a deterministic equation for the progress of these colonies. Thus, we add a stochastic (local) interaction and simulate the evolution of an Eden-like aggregate by using dynamical Monte Carlo methods. The growth curves of both deterministic and stochastic models are in excellent agreement with the experimental observations. The waiting times distributions, generated via our stochastic model, allowed us to analyze the role of mesoscopic events. We obtain log-normal distributions in the initial stages of the growth and Gaussians at long times. We interpret these outcomes in the light of cellular division events: in the early stages, the phenomena are dependent each other in a multiplicative geometric-based process, and they are independent at long times. We conclude that the main ingredients for a good minimalist model of tumor growth, at mesoscopic level, are intrinsic cooperative mechanisms and competitive search for space. © 2013 Elsevier Ltd.

A Cooperative and Adaptive Variable Neighborhood Search for the Multi Depot Vehicle Routing Problem with Time Windows

In this paper we propose two cooperation schemes to compose new parallel variants of the Variable Neighborhood Search (VNS). On the one hand, a coarse-grained cooperation scheme is introduced which is well suited for being enhanced with a solution warehouse to store and manage the so far best found solutions and a self-adapting mechanism for the most important search parameters. This makes an a priori parameter tuning obsolete. On the other hand, a fine-grained scheme was designed to reproduce the successful properties of the sequential VNS. In combination with the use of parallel exploration threads all of the best solutions and 11 out of 20 new best solutions for the Multi Depot Vehicle Routing Problem with Time Windows were found.

Thai students' engagement with cooperative learning in mathematics classrooms

Over the past decade, Thai schools have been encouraged by the Thai Ministry of Education to introduce more student-centred pedagogies such as cooperative learning into their classrooms (Carter, 2006). However, prior research has indicated that the implementation of cooperative learning into Thai schools has been confounded by cultural traditions endemic within Thai schools (Deveney, 2005). The purpose of the study was to investigate how 32 Grade 3 and 32 Grade 4 students enrolled in a Thai school engaged with cooperative learning in mathematics classrooms after they had been taught cooperative learning strategies and skills. These strategies and skills were derived from a conceptual framework that was the outcome of an analysis and synthesis of social learning, behaviourist and socio-cognitive theories found in the research literature. The intervention began with a two week program during which the students were introduced to and engaged in practicing a set of cooperative learning strategies and skills (3 times a week). Then during the next four weeks (3 times a week), these cooperative learning strategies and skills were applied in the contexts of two units of mathematics lessons. A survey of student attitudes with respect to their engagement in cooperative learning was conducted at the conclusion of the six-week intervention. The results from the analysis of the survey data were triangulated with the results derived from the analysis of data from classroom observations and teacher interviews. The analysis of data identified four complementary processes that need to be considered by Thai teachers attempting to implement cooperative learning into their mathematics classrooms. The paper concludes with a set of criteria derived from the results of the study to guide Thai teachers intending to implement cooperative learning strategies and skills in their classrooms.

Energy-Efficient Decentralized Cooperative Routing in Wireless Networks

Wireless adhoc networks transmit information from a source to a destination via multiple hops in order to save energy and, thus, increase the lifetime of battery-operated nodes. The energy savings can be especially significant in cooperative transmission schemes, where several nodes cooperate during one hop to forward the information to the next node along a route to the destination. Finding the best multi-hop transmission policy in such a network which determines nodes that are involved in each hop, is a very important problem, but also a very difficult one especially when the physical wireless channel behavior is to be accounted for and exploited. We model the above optimization problem for randomly fading channels as a decentralized control problem - the channel observations available at each node define the information structure, while the control policy is defined by the power and phase of the signal transmitted by each node. In particular, we consider the problem of computing an energy-optimal cooperative transmission scheme in a wireless network for two different channel fading models: (i) slow fading channels, where the channel gains of the links remain the same for a large number of transmissions, and (ii) fast fading channels, where the channel gains of the links change quickly from one transmission to another. For slow fading, we consider a factored class of policies (corresponding to local cooperation between nodes), and show that the computation of an optimal policy in this class is equivalent to a shortest path computation on an induced graph, whose edge costs can be computed in a decentralized manner using only locally available channel state information (CSI). For fast fading, both CSI acquisition and data transmission consume energy. Hence, we need to jointly optimize over both these; we cast this optimization problem as a large stochastic optimization problem. We then jointly optimize over a set of CSI functions of the local channel states, and a c- - orresponding factored class of control poli.