algorithm - Why is the state space the power set of the grid's dimensions? (edX CS 188.1x Artificial Intelligence) -

algorithm - Why is the state space the power set of the grid's dimensions? (edX CS 188.1x Artificial Intelligence) -

i'm self-learning edx course of study cs 188.1x artificial intelligence. since course of study concluded year ago, in "archive mode" , there no teaching staff help questions. means no credit finishing course, asking help "homework" question here okay.

in first homework assignment next question asked:

question 9: hive minds lost @ night night , command single insect. know maze, not know square insect start in. must pose search problem solution all-purpose sequence of actions such that, after executing actions, insect on exit square, regardless of initial position. insect executes actions mindlessly , not know whether moves succeed: if uses action move in blocked direction, remain is. example, in maze below, moving right twice guarantees insect @ exit regardless of starting position.

it asks size of state space. reply given 2^mn, m , n horizontal , vertical dimensions of maze. why reply powerfulness set of mn? in mind, bug can in 1 square @ beginning, , have 1 bug, know number of start states mn. number of start states != state space, , confused.

fyi - cost per move 1, , bug can move 1 square left, right, up, or downwards @ time. goal x (goal square).

okay - think got it.

set of subsets (power set*) right way think this. state space set of states.

1) definition of state:

"a state contains of info necessary predict effects of action , determine if goal state." (http://artint.info/html/artint_48.html)

the actions in scenario simple: left, right, up, down. possible movements bug make.

2) definition of solution:

solutions sequences of actions lead goal test beingness passed.

if permitted mn states, 1 each possible starting position bug in, have state space gave solutions valid discrete starting positions. but, solution must valid regardless of initial state of bug. means solution must work scenarios in bug could occupy any of mn available squares.

in other words, solutions must valid each , every subset (combination) of possible starting spaces, yields powerfulness set of mn, 2^mn.

why? because solutions valid given start state may not valid other start states. , problem requires find solutions valid all start states. why state space much larger mn though in reality our bug occupies 1 of mn positions upon initialization. because solution (sequence of moves) works when bug starts @ (1, 1) doesn't mean solution (sequence of moves) also work bug starting @ (2, 1).

bonus question: why isn't state space 1, total set each of mn squares 'has' bug (and bugs permitted move on top of each other)?

i tempted because sequence of moves gives goal state when bug can start @ all of mn possible positions, doesn't mean same sequence of moves gives goal state when bug starts @ (3, 2) or @ mn - 1 or mn - 2 etc. possible positions. definition must (a solution on starting points must solution on every finite subset of starting points).

so think reason evaluate starting states other "all boxes have bug" because solution generated evaluating state may not optimal. , in fact interpretation borne out homework gives admissible heuristics problem:

the maximum of manhattan distances goal each possible location insect in.

or

the minimum of manhattan distances goal each possible location insect in.

the case have 1 starting state bugs on boxes (with magic ability on top of each other) relaxed problem utilize define our heuristic. 1 time again definition of admissibility, since heuristic must not overestimate true (arc) cost of action, , since arc cost given manhattan distances, both heuristics above admissible. (the maximum case admissible because each possible location bug is, in fact, possible - max cost possible).

*if don't know powerfulness set means, need know powerfulness set set of subsets of given set. given 2^(size of set).

in other words, if have set of 3 balls {red, blue, green} , want know how many different subsets have, can calculate follows. subset either has element in (1), or doesn't (0). {0, 0, 1} subset of greenish ball, {1, 1, 1} subset of balls (yes, technically subset) , {0, 0, 0} subset of none of balls (again, technically subset). see number of subsets 2^3 = 8. or in our problem, 2^mn.

algorithm artificial-intelligence graph-algorithm state-space