Collaboration in AI Cheat Sheet (DRAFT) by lior1995

Non optimal
Algorithm: Priori­tized Planning -Expla­nation: Priori­tized Planning assigns priority levels to agents based on their importance and solves subpro­blems in a priori­tized order. It is complete, but the solutions may not be optimal due to the disruption caused by higher­-pr­iority agents to lower-­pri­ority agents' plans.
Efficient for solving multi-­agent pathfi­nding problems by priori­tizing agents based on their import­ance. Ineffi­cient for problems with confli­cting priorities or complex depend­encies.

Optimal
Algorithm: ICTS
Algorithm: CBS -Expla­nation: Two-level algorithm, first finds a confli­ct-free path assignment using a high-level search tree and then resolves conflicts at the low-level. It guarantees optimality when using optimal low-level solvers. Efficient for solving multi-­agent pathfi­nding problems with confli­cting paths and bottle­necks. Ineffi­cient for problems with a large number of agents or complex enviro­nments.
Algorithm: M-star -Expla­nation: A single­-agent pathfi­nding algorithm that uses lazy search to adapt to dynamic obstacles in grid-based enviro­nments. Efficient for solving single­-agent pathfi­nding problems in grid-based enviro­nments with an unbounded number of obstacles. Ineffi­cient for problems with a large number of agents or complex terrain.
Algorithm: A-star OD ID -Expla­nation: A-star OD is a variant of A-star where 1 agent moves every time. Deeper search but lower branching factors, hopefully can explore less of the tree this way.
Algorithm: EPE A-star (Enhanced Partial Expansion A-star) -Expla­nation: EPE A-star select­ively expands nodes, focusing on promising areas using a heursitic on actions, to reduce comput­ational overhead.

Simple Indepe­ndence Detection
1. Solve optimally each agent separately
2. While some agents conflict
  A.Merge confli­cting agents to one group
  B.Solve optimally new group

Indepe­ndence Detection
Try to avoid conflict with same cost before merge

Online Indepe­ndence Detection
Solve for every group of agents separa­tely, merge groups if necessary.
Advant­ages: Replan only required agents, Minimize distur­bance, maintain snapshot optima­lity.

Fact = a predicate, State = a conjun­ction of facts, The initial state: all that I know about the world
The goal: a conjun­ction of facts that I wish true,
Action = a method for moving between states
- Can have precon­ditions and effects

STRIPS - Problem is <Pr­edi­cates, Actions, Initial, Goal>
Approach 1- State Space Search. Can search Forward to the goal or backward from the goal. Possible heuris­tics: Delete relaxa­tio­n/A­bst­rac­tio­n(R­emove a predicate)
Approach 2- Partial order planning- try to achieve goals in parallel, Only make choices when conflicts occur.
Approach 3- SAT compil­ation.

MA-STRIPS - Replace Actions in strips with a set of actions per agent. It has different levels:
Centra­lized | Centra­lized but allow parallel execution| Decent­ralized observ­ations| Decent­ralized execution| Decent­ralized planning
Approach 1- STRIPS compil­ation: If agents can act in parallel, A in STRIPS will be the cartesian product of all A's.
Else, The possible actions are a unition of all actions.
In the parallel setting:
- Full knowledge of other agent’ abilities
- Global heuristic estimates, as in centra­lized planning
In the distri­buted setting:
- Partial knowledge of other agents’ abilities
- Local, less informed heuristic estimates
In the centra­lized setting:
- Agents represent a natural factoring of the problem
Can we plan in a mostly decoupled way?
Pros: - Can use regular STRIPS planner
Cons: - Does not fit a distri­buted setting
- Branching factor expone­ntial w. # of agents

Private actions affect and are affected by agent’s actions only.
Public actions affect or are affected by other agents.
Approach 2: Planning + CSP

Algorithm: Weighted A-Star - A-Star that has a weight factor to prioritize nodes close to the goal by increasing the weight of h in the formula.
Formula: f(n) = g(n) + w * h(n)
Algorithm: Suboptimal CBS -First expand the routes with the least conflicts OR use single agent A-Star for low leve serach OR use BFS for high level search.

● High level planning
○ Outcome: coordi­nation scheme
○ Approach: Solve a relaxed planning problem
● Grounding
○ Input: a coordi­nation scheme
○ Output: a set of private plans to follow the scheme
■ Or false, if not possible
● Notes High level planning
○ Done using a heuristic forward search (GBFS)
○ Each agent generates runs search locally using only private
actions to identify relevant states to publish
○ Uses heuristics to guide the search
● Notes Grounding
○ Grounding is done in parallel by all agents
○ Agents can use different heuris­tic­s/p­lanners

Replan Single
Plan optimally one by one for new agents
New agent avoids current agents’ plans

Replan Single Grouped
Plan optimally for new agents together (MAPF)
New agents avoids current agents’ plans

Replan All
Replans optimally all agents when new agents appear
+Is snapshot optimal- optimal solution assuming no new agent appear in the future
-May unnece­ssarily disturb agents

Possible objective functions: Sum of steps, Number of agents in graph at any time, Sum of steps over shortest path- all equal. Throughput at time x, Maximal service ration (ratio between shortest path and actual path).

● Graph to model the intera­ction between actions
● Nodes correspond to actions
● An aedge (a1, a2) exists iff at least 1 of the following hold
○ a1 achieves a precon­dition for a2 (or the other way around)
○ a1 destroyed a precon­dition for a2 (or the other way around)
○ a1 and a2 have confli­cting effects
● Key: a partition of the AG induces MA-STRIPS

Algorithm for agents
1.While (not done)
1.1. Handle received messages
1.2. Extract best state s from OPEN
1.3. For every action a of this agent
1.3.1. s’ = genera­te(a,s)
1.3.2 Add s’ to OPEN
1.3.3. If a is public, broadcast it

● Can be optimal! But needs halting mechanism.
● Distri­buted with distri­buted heuristics
● Sometimes, MAFS achieves super linear speedup since it exploits
the structure of the problem