# Multiple Mobile Robots Coordination
###### tags: `archived` `research` `solab`

[TOC]

### Multiple Mobile Robot Systems
#### Advantages comparing to single-robot[^assmc]:
* Better ==spatial distribution==.
* Can achieve better overall system performance. The performance metrics could be the total time required to complete a task or the energy consumption of the robots.
* Robustness that can benefit from ==data fusion and information sharing== among the robots, and fault-tolerance that can benefit from information redundancy.
* Can have a ==lower cost==. Using a number of simple robots can be simpler (to program), cheaper (to build) than using a single powerful robot (that is complex and expensive) to accomplish a task.
* Can exhibit better ==system reliability, flexibility, scalability and versatility.== Robots with diverse abilities can be combined together to deal with complex task, and one or several robots may fail without affecting the task completion.

#### General Processes
1. Task planning:
Task decomposition -> Task allocation (optimal assignment problem)
2. Motion planning (包含multi-robot space sharing problem)

#### Homogeneous or Heterogeneous[^assmc]:
Whether the ==capabilities== are identical or not.

### Multi-Robot Coordination

#### Coordination 的分類[^mscf]

* Inspired by multi-agent systems (MAS). But a MRS can not be simply considered as a special case of a multiagent system, because of the issue arising when dealing with a physical environment.
* _Coordination Level_: We consider strong (weak) coordination as a form of coordination that relies (does not rely) on a ==coordination protocol==. The actions performed by each robotic agent take into account the actions executed by the other robotic agent.
* _Organization Level_: (Decision making[^assmc]: can be regarded as a cognitive process resulting in the selection of a course of action among several alternative scenarios. 這裡應該指的就是 motion planning 的時候)
* ==Distributed== system:
* >可以從別人拿資訊，別人無法幫他做決定，他也不會幫別人做決定
* Agents are ==completely autonomous== in the decision process with respect to each other
* There is still some kind of communication
* A leader does not exist.
* Pros: robust to communication failures and robot malfunctioning
* Cons[^assmc]: Suboptimal solutions.
* Test-beds:
* Foraging
* heterogeneous robots, loosely coupled subtasks: hazardous waste cleanup mission[^hrls]
* cooperative cleaning: vacuum and sweeper[^gscb]
* Box pushing
* pulling many sticks out of ground (too long to pull by only one robot)[^ctel]
* Multi-target observation[^mto]
* Exploration
* Soccer
* Strongly centralized system: decisions are taken by the same predefined leader agent during the entire mission duration
* Weakly centralized system: more than one agent is allowed to take the role of the leader during the mission.
* Centralized[^assmc]:
* Pros: Globally optimal plans can be produced.
* Cons: Inefficient for large teams. Not robust to dynamic environments or failures.

[^mscf]: A. Farinelli, L. Iocchi and D. Nardi, "Multirobot systems: a classification focused on coordination," in IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), vol. 34, no. 5, pp. 2015-2028, Oct. 2004.
[^hrls]: L. E. Parker, “ALLIANCE: An architecture for fault tolerant multirobot
cooperation,” IEEE Trans. Robot. Automat., vol. 14, pp. 220–240, Apr. 1998.
[^mto]: B. B. Werger and M. J. Mataric, “Broadcast of local eligibility for multitarget observation,” in Proc. DARS, 2000, pp. 347–356.
[^ctel]: A. J. Ijspeert, A. Martinoli, A. Billard, and L. M. Gambardella, “Collaboration through the exploitation of local interactions in autonomous
collective robotics: The stick pulling experiment,” in Autonomous
Robots. Norwell, MA: Kluwer, 2001, vol. 11, pp. 149–171.
[^gscb]:D. Jung and A. Zelinsky, “Grounded symbolic communication between
heterogeneous cooperating robots,” Auton. Robots, vol. 8, no. 3, pp.
269–292, 2000.

#### Communication 的分類[^assmc]
* Explicit
* pros: accuracy of informations
* cons: communication load of the system increases as number of robots increases
* Implicit
* Requires the robot to perceive, model and reason others' behaviour.
* pros: ==stability, reliability and fault tolerance of the whole MRS are better (than explicit).==
* cons: information is not completely reliable
* Examples mentioned in this paper:
* Soccer
* Box pushing
* Leader-follower
* Search algorithm
[^assmc]:Yan, Z., Jouandeau, N., & Cherif, A. A. (2013). A Survey and Analysis of Multi-Robot Coordination. International Journal of Advanced Robotic Systems. https://doi.org/10.5772/57313

#### 測試情境 Test-bed[^mscf]
* Foraging and Coverage
* Multi-target Obervation
* Box Pushing and ==Object Transportation==:
* Object transportation is frequently used as test-bed for issues like ==motion coordination== and ==formation control==.
* Exploration and Flocking

#### 名詞定義
* Network Robot Systems (NRS)[^nrsa]:
Includes the following elements:
* Physical embodiment: Any NRS has to have at least a physical robot which incorporates hardware and software capabilities
* Autonomous capabilities: A physical robot must have autonomous capabilities to be considered as a basic element of a NRS.
* Network-based cooperation: The robots, environment sensors and humans must communicate and cooperate through a network.
* Environment sensors and actuators: Besides the sensors of the robots, the environment must include other sensors, such as vision cameras and laser range finders, and other actuators, such as speakers and flickers
* Human-robot interaction: In order to consider a system as NRS, the system must have a human-robot related activity.

[^nrsa]:"Network robot systems," Alberto Sanfeliu, 2008

* Market-Based Approach[^mbmc]
* ==(Task planning)==
* The team is given an objective that can be decomposed into subcomponents achievable by individuals or subteams. The team has access to a limited set of ==resources== with which to meet this objective.

* A global objective function quantifies the system designer's preferences over all possible solutions.

* An individual utility function (or cost function) specified for each robot quantifies that robot's preferences for its individual resource usage and contributions towards the team objective given its current state. Evaluating this function cannot require global or perfect information about the state of the team or team objective. Subteam preferences can also be quantified through a combination of individual utilities (or costs).

* A mapping is defined between the team objective function and individual and subteam utilities (or costs). This mapping addresses how the individual production and consumption of resources and individuals’ advancement of the team objective affect the overall solution.

* Resources and individual or subteam objectives can be ==redistributed== using a mechanism such as an ==auction==. This mechanism accepts as input team-mates’ bids, which are computed as a function of their utilities (or costs), and determines an outcome that maximizes the mechanism-controlling agent's utility (or minimizes the cost). In a well-designed mechanism, maximizing the mechanism-controlling agent's utility (or minimizing cost) results in improving the team objective function value.

[^mbmc]: (M. B. Dias, R. Zlot, N. Kalra and A. Stentz, "Market-Based Multirobot Coordination: A Survey and Analysis," in Proceedings of the IEEE, vol. 94, no. 7, pp. 1257-1270, July 2006.)

* Collective Movement of Mobile Robots[^ascm]:
* Collective movement of mobile robots is the problem of how to control a group of robots making them move as a group, in a cohesive way, towards a common direction.
[^ascm]: Navarro, I., & Matía, F. (2013). A Survey of Collective Movement of Mobile Robots. International Journal of Advanced Robotic Systems. https://doi.org/10.5772/54600

### Multi-objective Optimization
#### Complex System[^oics]
A complex system is defined as an assembly of interacting members that is difficult to understand as a whole. A system is difficult to understand if an individual cannot understand the details of all members and all interactions between members.

#### Coupling[^oics]
Coupling variables are artifacts of decomposition; they do not exist in the system’s original design problem statement.

#### Allison[^oics]
These are single level formulations—that is, all decision making is centralized and performed by a ==single optimizer==.

[^oics]:Allison, J., Kokkolaras, M., & Papalambros, P. (2008). On the Impact of Coupling Strength on Complex System Optimization for Single-Level Formulations. 265–275. https://doi.org/10.1115/detc2005-84790