Search

Tasks in the real world are complex and often require multiple robots to collaborate to be serviced. In many cases, a task might require different sensory inputs and actuation outputs. However, allocating a large variety of sensors and/or actuators on a single robot is not a cost-effective solution—robots with different attributes must be considered. In this paper, we study coalition formation for such a set of heterogeneous robots to be allocated instantaneously to a set of tasks. Our proposed solution employs a hedonic coalition formation strategy based on a weighted bipartite matching algorithm. In our setting, a hedonic coalition game, a topic rooted in game theory, is used to form coalitions by minimizing the total cost of the formation and maximizing the overlap between required and allocated types of robots for each of the tasks. This approach guarantees a polynomial time complexity and Nash-stability. Numerical results show that our approach finds similar quality near-optimal solutions to existing approaches while significantly reducing the time to find them. Moreover, it easily scales to large numbers of robots and tasks in negligible time (1.57 sec. with 2000 robots and 400 tasks).

Precision agriculture is the collection of hardware and software technologies that allow a farmer to make informed, differentiated decisions regarding agricultural operations such as planting, fertilizing, pest control, and harvesting. In recent years, advances in agricultural machinery and the emergence of agricultural robots continuously increased the resolution at which differentiated treatment is possible. This creates a corresponding need for information at a fine spatial and temporal resolution. Autonomous multi-robot systems (e.g., unmanned ground and aerial vehicles) are some of the most promising approaches for such information collection in open-air farms. In this paper, we survey the current state and challenges of multi-robot information gathering for precision agriculture, with a special focus on maximizing information and ensuring the security of the collected data while simultaneously keeping energy consumption in check.

Robots currently available in the market are somewhat limited in their capabilities, which makes it difficult for a single robot to handle many real-world tasks that are inherently complex. Thus, it becomes necessary to engage multiple robots which might form coalitions to complete such complex tasks. In this paper, we consider the well-known NP-hard problem of forming coalitions with the goal of instantaneous allocation (IA) of a group of robots to a set of tasks for optimal completion of the tasks. With the goal of bringing similar robots together to form coalitions, we use a correlation clustering technique, which uses a Linear Programming-based graph partitioning approach along with a region growing strategy. Our proposed approach is shown to gracefully handle both cost and utility-based objective functions for task allocation. We demonstrate that the resulting algorithm is fast and efficient in allocating (near) optimal robot coalitions to tasks. Furthermore, it outperforms two existing approaches in terms of execution times while yielding similar new-optimal solutions.

The complexity of a vast number of real world tasks provides a great challenge for the currently available robots due to their limited capabilities. Thus, multiple robots would need to form...

In a coordinated multi-robot information sampling scenario, robots often share their collected information with others for a better prediction. As with any other online data sharing technique, data integrity is a concern, but it has not yet been addressed in the multi-robot information sampling literature. In this paper, we study how to secure the information being shared among the robots in such a multi-robot network against integrity attacks and what is the cost of integrating such security techniques. To this end, we propose a Blockchain-based information sharing protocol that helps the robots reject fake data injection by a malicious entity. On the other hand, optimal information sampling is a compute-intensive technique and so are the popular Blockchain-based consensus protocols. Therefore, we also study the impact of adding such a security protocol on the execution time of the sampling algorithm, which in turn effects the energy spent by the robots. Results show that our proposed technique is effective against such data tampering attempts while the effect of the added computation varies largely on the consensus protocol used.

In this paper, we study the problem of allocating multiple heterogeneous robots to tasks. Due to the limited capabilities of the robots, a task might need more than one robot to complete it. The fundamental problem of optimally partitioning the set of n robots into m disjoint coalitions for allocating to m tasks is proven to be NP-hard. To solve this computationally intractable problem, we propose a distributed hedonic game formulation, where each robot decides to join or not join a team based on the other robots allocated to that particular task. It uses a bipartite matching technique to establish an initial set of coalitions before letting the robots coordinate asynchronously and change teams if desired. Our proposed solution is proved to converge to a Nash-stable solution. Results show that our proposed approach is fast and handles asynchronous robot-to-robot communication while earning more utility (up to 23%) than an existing technique in the majority of the test cases.

We consider the NP-hard problem of multirobot informative path planning in the presence of communication constraints, where the objective is to collect higher amounts of information of an ambient phenomenon. We propose a novel approach that uses continuous region partitioning into Voronoi components to efficiently divide an initially unknown environment among the robots based on newly discovered obstacles enabling improved load balancing between robots. Simulation results show that our proposed approach is successful in reducing the initial imbalance of the robots’ allocated free regions while ensuring close-to-reality spatial modeling within a reasonable amount of time.

Communication is one of the most popular and efficient means of multi-robot coordination. Due to potential real-world constraints, such as limited bandwidth and contested scenarios, a communication strategy requiring to send, for example, all n bits of an environment representation might not be feasible in situations where the robots’ data exchanges are frequent and large. To this end, we propose and implement lightweight, bandwidth-efficient, robot-to-robot communication protocols inspired by communication complexity results for data synchronization without exchanging the originally required n bits. We have tested our proposed approach both in simulation and with real robots. Simulation results show that the proposed method is computationally fast and enables the robots to synchronize the data (near) accurately while exchanging significantly smaller amounts of information (in the order of log n bits). Real-world experiments with two mobile robots show the practical feasibility of our proposed approach.

Cryptographic operations involved in securing communications are computationally intensive and contribute to energy drain in mobile devices. Thus, varying the level of security according to the user’s location may provide a convenient solution to energy management. Context-adaptive energy-aware security allocation for mobile devices is modeled in this paper as a combinatorial optimization problem. The goal is to allocate security levels effectively so that user utility is maximized while bounding the maximum energy cost to a constant E. Although the offline version of the problem has been previously studied in the literature where both the security levels and the locations to which a user may travel to is known a priori, this is the first work that formulates and solves an online version of the problem where the locations may be known a priori but the security levels are revealed only upon reaching the locations. We provide two different algorithms for the solution of this online problem by mapping it to the online multi-choice knapsack problem. We study competitive ratios of our two algorithms by comparing the solutions they yield to the optimal solution obtained for the corresponding offline problem. We also present simulation experiments on realistic datasets to validate the scalability and efficiency of our approaches (taking in order of milliseconds for up to 100 locations and providing near-optimal competitive ratios).

We consider the problem of configuration formation in modular robot systems where a set of modules that are initially in different configurations and located at different locations are required to assume appropriate positions so that they can get into a new, user-specified, target configuration. We propose a novel algorithm based on (sub)graph isomorphism, where the modules select locations or spots in the target configuration using a utility-based framework, while retaining their original configuration to the greatest extent possible, to reduce the time and energy required by the modules to disconnect and connect multiple times to form the target configuration. We have shown analytically that our proposed algorithm is complete and guarantees a Pareto-optimal allocation. Experimental simulations of our algorithm with different numbers of modules in different initial configurations and located initially at different locations, show that the planning time of our algorithm is nominal (order of msec for 100 modules). We have also compared our algorithm against a market-based allocation algorithm and shown that our proposed algorithm performs better in terms of time and number of messages exchanged.

We propose a lightweight and fast learning algorithm for classifying the features of an unknown terrain that a robot is navigating in. Most of the existing research on unknown terrain classification by mobile robots relies on a single powerful classifier to correctly identify the terrain using sensor data from a single sensor like laser or camera. In contrast, our proposed approach uses multiple modalities of sensed data and multiple, weak but less-complex classifiers for classifying the terrain types. The classifiers are combined using an ensemble learning algorithm to improve the algorithm’s training rate as compared to an individual classifier. Our algorithm was tested with data collected by navigating a four-wheeled, autonomous robot, called Explorer, over different terrains including brick, grass, rock, sand, and concrete. Our results show that our proposed approach performs better with up to 63% better prediction accuracy for some terrains as compared to a support vector machine (SVM)-based learning technique that uses sensor data from a single sensor. Despite using multiple classifiers, our algorithm takes only a fraction (1/65) of the time on average, as compared to the SVM technique.

Tasks in the real world are complex in nature and often require multiple robots to collaborate in order to be accomplished. However, multiple robots with the same set of sensors working together might not be the optimal solution as one task might require different sensory inputs and actuation outputs. On the other hand, putting all types of sensors and/or actuators on a single robot is not a cost-effective solution. Therefore, multiple robots with different capabilities need to coordinate and form teams in order to accomplish such tasks. In this paper, we study the coalition formation problem for task allocation with multiple heterogeneous (equipped with different sets of sensors) robots. We use a hedonic coalition formation framework, rooted in game theory, to solve the mentioned problem. Our proposed algorithm aims to minimize the total cost of the formed coalitions and to maximize the matching between the required and the allocated types of robots to the tasks. Simulation results show that it produces near-optimal solutions in a negligible amount of time (0.19 ms. with 100 robots and 10 tasks).

In this paper, we study the NP-Hard problem of multi-robot coalition formation for task allocation. To tackle this notoriously difficult problem, we model it as a variant of classical bipartite matching, which we call One-To-Many Bipartite Matching (OTMaM). Unlike the classical bipartite matching techniques used for matching a unique robot to a unique task, in the OTMaM problem, we let multiple robots to be matched to a single task while restricting the opposite. To this end, we propose a novel heuristic algorithm that allocates robots to tasks by finding mutually best robot-task pairs. Our algorithm provides a similar theoretical worst-case approximation ratio and guarantees a better worst-case time complexity than a comparable algorithm from the literature. The proposed approach in this paper is proved to be deterministic and the resultant matching is perfect. Simulation results also demonstrate the scalability of the presented algorithm (taking less than 1 millisecond with 100 robots and 10 tasks).

In this paper, we study the multi-robot task allocation problem where a group of robots needs to be allocated to a set of tasks so that the tasks can be finished optimally. One task may need more than one robot to finish it. Therefore the robots need to form coalitions to complete these tasks. Multi-robot coalition formation for task allocation is a well-known NP-hard problem. To solve this problem, we use a linear-programming based graph partitioning approach along with a region growing strategy which allocates (near) optimal robot coalitions to tasks in a negligible amount of time. Our proposed algorithm is fast (only taking 230 secs. for 100 robots and 10 tasks) and it also finds a near-optimal solution (up to 97.66% of the optimal). We have empirically demonstrated that the proposed approach in this paper always finds a solution which is closer (up to 9.1 times) to the optimal solution than a theoretical worst-case bound proved in an earlier work.

Speed, area and power are the main parameters of modern day's devices. Adders are the main component of all digital devices and play a crucial role in signal processing. There are different types of adder for different type of work and environment. Time by time new adders was invented to minimize the basic problems i.e. Speed, Area and Power. Among them Carry Select Adder is the most trending area of research. All the work that has been done on adder is to optimize three parameters mentioned earlier. CSlA has better performance regarding propagation delay but problem arise with its chip area and power consumption capability. In this paper we have discussed about different types of basic adder and then briefly described about different types of Carry Select Adder (CSlA). Later we have proposed a modified SQRT model changing its sequence and the whole comparison has been carried out in Xilinx 14.7 ISE environment and coded using Verilog HDL. Specific graph and table of the values are given for better comparison.

We study the problem of adaptive locomotion learning for modular self-reconfigurable robots (MSRs). MSRs are mostly used in unknown and difficult-to-navigate environments where they can take a completely new shape to accomplish the current task at hand. Therefore it is almost impossible to develop the control sequences for all possible configurations with varying shape and size. The modules have to learn and adapt their locomotion in dynamic time to be more robust in nature. In this paper, we propose a Q-learning based locomotion adaptation strategy which balances exploration versus exploitation in a more sophisticated fashion. We have applied our proposed strategy mainly on the ModRED modular robot within the Webots simulator environment. To show the generalizability of our approach, we have also applied it on a Yamor modular robot. Experimental results show that our proposed technique outperforms a random locomotion strategy and it is able to adapt to module failures.

Modular self-reconfigurable robots (MSRs) are mostly used in environments where it is difficult to navigate and explore otherwise. Especially, the shape-changing ability of MSRs makes them more dexterous in these situations compared to fixed-body robots. But when the MSR forms a new configuration, usually, the locomotion pattern for that particular configuration is not known by its constituting robotic modules. The main challenge for modules is to learn how to move in that specific configuration within a reasonable amount of time. In this paper, we study the problem where an MSR needs to learn its movement pattern on-the-fly. To solve this problem, we have proposed a game theoretic solution based on multi-agent reinforcement learning using which the constituting modules distributedly learn the best actions that they need to perform to travel more distance in less time. We have implemented this approach in simulation on both ModRED and Yamor MSR platforms. Results show that our approach performs better (up to 7.86 times) in terms of average speed achieved for most of the tested configurations as compared to an existing locomotion learning approach.

This paper presents a homogeneous modular robot system design based on four per-module degrees of freedom (DOF), including a prismatic DOF to increase the versatility of its reconfiguration and locomotion capabilities. The ModRED (Modular Robot for Exploration and Discovery) modules are developed with rotary-plate genderless single sided docking mechanisms (RoGenSiD) that allow chain-type configurations and lead towards hybrid-type configurations. Various locomotion gaits are simulated through the Webots robot simulator and implemented in the real ModRED system. This work also addresses the problem of dynamic reconfiguration in a modular self-reconfigurable robot (MSR). The self-reconfiguration problem is modeled as an instance of the graph-based coalition formation problem. We formulate the problem as a linear program that finds the “best” partition or coalition structure among a set of ModRED modules. The technique is verified experimentally for a variety of settings on an accurately simulated model of the ModRED robot within the Webots robot simulator. Our experimental results show that our technique can find the best partition with a reasonably low computational overhead.

We study the problem of self-assembly in heterogeneous multi-agent systems where a set of agents initially randomly located in the environment need to form a user-specified pattern. The agents are heterogeneous in nature, i.e., each agent can only become the neighbor of a specific set of agents in the target pattern. To solve the self-assembly problem, we propose a novel technique, based on a constrained bipartite graph matching algorithm which allocates the agents to unique spots in the target pattern and moreover the allocation is done in such a way that any two allocated neighboring agents are compatible with each other. After the allocation is done, agents move to their unique allocated spots to assume their positions and form the target pattern. Experimental results show that our approach takes very nominal time to execute (in order of milliseconds for 100 agents).

We consider the configuration formation problem in modular robotic systems where a set of singleton modules that are spatially distributed in an environment are required to assume appropriate positions so that they can configure into a new, user-specified target configuration, while simultaneously maximizing the amount of information collected while navigating from their initial to final positions. Each module has a limited energy budget to expend while moving from its initial to goal location. To solve this problem, we propose a budget-limited, heuristic search-based algorithm that finds a path that maximizes the entropy of the expected information along the path. We have analytically proved that our proposed approach converges within finite time. Experimental results show that our planning approach has lower run-time than an auction-based allocation algorithm for selecting modules' spots.

An important aspect of successful locomotion in Modular Self-reconfigurable Robots (MSRs) is to be able to autonomously coordinate the movement of the modules so that the robot can move towards the goal. We consider the locomotion problem in a partially distributed setting where multiple MSRs (disconnected groups of connected modules) are within the communication range of each other and modules do not have a priori information about other modules that belong to the same configuration. Coordinating the movement of modules in such a setting becomes a challenging problem because of the limited perception and computation resources available on each module. To address these problems, we propose a strategy that first combines neighbor-to-neighbor message passing techniques via infrared and wireless communication to enable each module to autonomously determine the set of modules that belong to the same MSR. The strategy then uses a distributed leader election algorithm to identify the leader, which thereafter coordinates the actions of the modules in its configuration. We have verified the performance of our approach using an accurately simulated model of the ModRED MSR within the Webots simulator and in the embedded system of ModRED (This work was done as part of the ModRED project which is supported by NASA EPSCoR grant no. NNH11ZHA003C.). It is shown that our strategy can successfully determine the set of connected modules, elect a leader for each configuration and coordinate the locomotion of MSRs for different numbers of modules.

We consider the problem of reconfiguration planning in modular robots. Current techniques for reconfiguration planning usually specify the destination configuration for a modular robot explicitly.We posit that in uncertain environments the desirable configuration for a modular robot is not known beforehand and has to be determined dynamically. In this paper, we consider this problem of how to identify a new ‘best’ configuration when a modular robot is unable to continue operating efficiently in its current configuration.We build on a technique that enumerates all the possible partitions of a set of modules requiring reconfiguring as a coalition structure graph (CSG) and finds the ‘best’ node in that graph. We propose a new data structure called an uncertain CSG (UCSG) that augments the CSG to handle uncertainty originating from the motion and performance of the robot. We then propose a new search algorithm called search UCSG that intelligently prunes nodes from the UCSG using a modified branch and bound technique. Experimental results show that our algorithm is able to find a node that is within a worst bound of 80% of the optimal or best node in the UCSG while exploring only half the nodes in the UCSG. The time taken by our algorithm in terms of the number of nodes explored is also consistently lower than existing algorithms (that do not model uncertainty) for searching a CSG.

We consider the problem of predicting and learning the efficiency of navigation tasks being performed by a robot in an initially unknown or partially known, unstructured environment. Predicting the efficiency of a task is a crucial problem in unstructured environments as it enables the robot(s) to decide whether it is feasible to perform the task under the current environment conditions and within its available resources such as battery power. This problem is non-trivial as robot's performance changes during operation based on its operational conditions, available battery change, etc. In this paper, we have addressed this problem by using a learning-based technique that the robot uses to predict its expected efficiency for performing a new task based on the task's similarity and recentness with previously performed tasks. Experimental results show that our proposed technique can successfully predict the efficiency of a task from previous task experiences and this prediction gets better with number of tasks performed. We have also shown empirically that our model is robust to changes in environmental conditions such as localization and wheel slip noise.

We consider the problem of dynamic coalition formation among a set of agents where the value function of the agents is constrained by the size of a coalition - larger coalitions are able to get higher value but only up to a certain fixed coalition size, denoted by n_max. The objective of the coalition formation problem is to determine a partition of the agent set that gives the highest utility to the agents. This problem is non-trivial as the set of partitions that needs to be explored grows exponentially with the number of agents and an exhaustive search in the space of partitions makes the problem intractable. To address this problem, we first provide a formal framework to model the coalition formation problem using a coalition structure graph (CSG). We then propose a branch and bound based algorithm called bottom Up CSG Search that searches for the optimal partitions or coalition structures among the nodes of CSG while pruning nodes that are not going to lead to the optimal coalition structure. We have provided analytical results related to the completeness, anytime-nature and time complexity of our algorithm. We have also verified the performance of our algorithm for a dynamic reformation problem where a set of physical e-puck robots starting from arbitrary positions form sub-teams that maximize their utility. Our experimental results show that our proposed algorithm performs better in terms of number of nodes generated and the time required to find the optimal coalition structure or partition than existing CSG-search algorithms.

This paper proposes a distributed algorithm for circle formation by a system of mobile robots. Each robot observes the positions of other robots and moves to a new position. Eventually they form a circle. The robots do not store past actions. They are anonymous and cannot be distinguished by their appearance and do not have a common coordinate system (origin and axis) and chirality (common handedness). Most of the earlier works assume the robots to be dimensionless (points). In this paper a robot is represented as a unit disc (fat robot). The robots are assumed to be transparent in order to achieve full visibility. However, a robot is considered as a physical obstacle for another robot. The robots execute the algorithm asynchronously.

This paper proposes a distributed algorithm for circle formation by multiple autonomous mobile robots. The vision of each robot is limited to a maximum distance. The robots do not store past actions or records of past data. They are anonymous and cannot be distinguished by their appearances. All robots agree on a common origin and axes. Earlier works report algorithms for gathering of multiple autonomous mobile robots in limited visibility considering the robots to be dimensionless or points. This paper models a robot as a unit disc (fat robot). The algorithm presented in this paper also assures that there is no collision among the robots. The robots do not share a common clock. They execute the algorithm asynchronously.

To achieve coordination in a multi-robot system, the robots typically resort to some form of communication among each other. In most of the multi-robot coordination frameworks, high-level coordination strategies are studied but ‘how’ the ground-level communication takes place, is assumed to be taken care of by another program. In this paper, we study the communication routing problem for large multi-robot systems where the robots have limited communication ranges. The objective is to send a message from a robot to another in the network, routed through a low number of other robots. To this end, we propose a communication model between any pair of robots using peer-to-peer radio communication. Our proposed model is generic to any type of message and guarantees a low hop routing between any pair of robots in this network. These help the robots to exchange large messages (e.g., multi-spectral images) in a short amount of time. Results show that our proposed approach easily scales up to 1000 robots while drastically reducing the space complexity for maintaining the network information.

We consider the problem of information collection from a polygonal environment using a multi-robot system, subject to continuous connectivity constraints. In particular, the robots, having a common radius of communication range, must remain connected throughout the exploration maximizing the information collection. The information gained through the exploration of the terrain is wirelessly transmitted to a base station. The base station performs the centralized planning of informative paths for the robots based on the information collected by them and thereafter, the robots follow these paths. This paper formulates the problem of multi-robot informative path planning under continuous connectivity constraints as an integer program leveraging the ideas of bipartite graph matching and minimal node separators. Theoretical analysis of the proposed solution proves that the informative paths will be collision-free and will be free of both livelock and deadlock. Experimental results demonstrate the low computational requirements of our algorithm for planning the informative paths, taking only about 0.75 sec. for planning a joint set of collision-free informative locations for 10 robots.