Decentralized task allocation in a multi-agent system is attracting attention in recent years. Applications such as the cooperation of soccer or rescue robots and UAVs controlling in military missions are some problems that increase the need for fast decentralized algorithms. When talking about robots, we should consider that the sensors are noisy and have a limited range. These conditions turn the environment from fully observable to partially observable. By admitting this fact, we should also accept the complexity of working with ambiguous data. Using a subjective view gives us the opportunity of having a decentralized system. Researchers utilized the subjective approach to solve the spatial task allocation problem (SPATAP) in a fully observable environment. Our goal is to solve SPATAP in a partially observable environment in a decentralized way. In an SPATAP instance, we deal with a grid where there might be some tasks in every location with a certain probability. A subjective view means each agent infers other agents' behaviors and predicts their actions. A self-absorbed agent approach and an extension of Distributed Value Function (DVF) were offered, based on a subjective view in the past. In the offered self-absorbed approach, each robot considers itself the only agent in the world and regards others as noise or uses a uniform distribution to predict others' behaviors. In this dissertation, the idea of the self-absorbed is extended to a partially observable environment. We use Partially Observable Monte-Carlo Planning (POMCP) to predict the value of the following belief and call the resulting algorithm Partially Observable Self-absorbed Agent (POSA). In this research, an extension of DVF, which was used in fully observable environments (without communication), is extended to partially observable environments and is called Partially Observable Distributed Value Function (PODVF). PODVF extends the presence probability of agents to a continuous world using a similarity measure of two distributions and Bhattacharya distance. The experimental results indicate the suitable accuracy of POSA and PODVF, but both algorithms are time-consuming. To solve the low-speed problem, some modifications are performed in POMCP to make it suitable for a decentralized multi-agent environment. Two ideas are offered and eva‎luated: The first builds a search tree with single actions of the decision maker, which we call Single-action POMCP (SPOMCP). Another, called Global-action POMCP (GPOMCP), uses action profiles to make a tree. When building a SPOMCP tree, the agent encodes the effect of others' actions in the tree implicitly using a greedy approach. GPOMCP agent, which builds a subjective search tree with joint actions, utilizes a coordinate-wise optimization to estimate its single action value and the value of other agents' actions and guesses the approximate best action vector. Simulations show that SPOMCP and GPOMCP have high-quality results and fast running times. These algorithms can reach the quality of the centralized algorithm POMCP while consuming much less time per iteration.

مازيار پالهنگ

ناصر مزيني

مجيد نيلي احمدآبادي , محمدحسين منشئي , حسين فلسفين