What is Search About and For
Search is about choice and decision making; it is for many different things, such as planning and assigning.
Planning: sequences of actions
We care about the path to the goal. Paths have different depths.
Identification: assignments
We care about the goal itself, not the path.
All paths have the same depths.
For example, a taxi firm assigns n taxis to n customers, where the search tree’s depth is n.
Example: Assignment
Task A Task B Task C Agent1 3 7 2 Agent2 9 3 1 Agent3 2 2 1
Agent 1
AB
C
Agent 2
BCACA CBCABA
Agent 3
B
Branch and Bound
Idea: maintain the best (lowest‐cost) path to a goal found so far. If the search encounters a path whose cannot produce a solution with better cost (i.e., its lower bound >= cost of the maintained goal path), then discard that path.
It is very applicable when there are many paths to a goal.
It is very applicable when there is one fairly good solution
available beforehand.
If no bounds are available, the algorithm degenerates to uniform cost search.
Example: Branch and Bound
Task A Task B Task C Agent1 3 7 2 Agent2 9 3 1 Agent3 2 2 1
It is allowed to allocate multiple agents to one task when calculating lower bound.
Agent 2
Agent 1
A lb: 3+1+1
B lb: 7+1+1
C lb: 2+1+1
Agent 3
Best so far: 7 (TA ‐> A1, TB‐>A2, TC‐>A3
Example: Branch and Bound
Task A Task B Task C Agent1 3 7 2 Agent2 9 3 1 Agent3 2 2 1
It is allowed to allocate multiple agents to one task when calculating lower bound.
Agent 2
Itexploresthenodewiththe best lb (lower bound)
Agent3
Agent 1
C lb: 2+1+1 B lb: 5+1
Best so far: 7 (TA ‐> A1, TB‐>A2, TC‐>A3
A lb: 3+1+1
B lb: 7+1+1
A lb: 11+1
Example: Branch and Bound
Task A Task B Task C Agent1 3 7 2 Agent2 9 3 1 Agent3 2 2 1
It is allowed to allocate multiple agents to one task when calculating lower bound.
Agent 2
Itexploresthenodewiththe best lb (lower bound).
Agent3
Agent 1
B lb: 7+1+1
C lb: 2+1+1
Best so far: 7 (TA ‐> A1, TB‐>A2, TC‐>A3
A lb: 3+1+1
Blb:6+1 C lb:4+1 Alb:11+1 Blb:5+1
Example: Branch and Bound
Task A Task B Task C Agent1 3 7 2 Agent2 9 3 1 Agent3 2 2 1
Best so far: 6 (TA ‐> A1, TB‐>A3, TC‐>A2
It is allowed to allocate multiple agents to one task when calculating lower bound.
Agent 2
Itexploresthenodewiththe best lb (lower bound).
Agent3
B cost: 6
Agent 1
B lb: 7+1+1
C lb: 2+1+1
Best so far: 7 (TA ‐> A1, TB‐>A2, TC‐>A3
A lb: 3+1+1
Blb:6+1 C lb:4+1 Alb:11+1 Blb:5+1