Module 3
IN COMPLEX ENVIRONMENTS
Intelligent Agent:
Anything that may be thought of as sensing its surroundings through sensors and acting upon
them through actuators is an agent.
A robotic agent have different motors for cameras, actuators and infrared range finders for
sensors.
File contents, network packets, and human input (keyboard, mouse, touchscreen, and voice)
are all received by a software agent as sensory inputs.
writes files, sends network packets, displays data, or makes noises to interact with the
surroundings.
The term "percept" describes the data that an agent's sensors are picking up.
The actions taken by an agent are determined by its pre-existing knowledge and the entire
percept sequence that has been observed thus far, not by anything it hasn't seen.
agents use sensors and actuators to interact with their surroundings
Defining the Task Environment:
Task environments can be thought of as the "problems" that rational agents are supposed to
solve.
Workplace Situation For instance, when defining the performance basic vacuum cleaner
agent, measure the surroundings and actuators and sensors, we had to be specific.
The description of PEAS (Performance, Environment, Actuators, Sensors)
Task Environment Characteristics
Discrete(4.1):
The environment's condition, the way time is managed, and the agent's perceptions and
behaviors are all covered by the discrete/continuous divide.
There are distinct perceptions and actions in chess as well.
Digital camera input is separate.
Issues with Local and Optimization
involving hill climbing
The annealing simulation
for local beams using evolutionary methods
Continuous(4.2): The other vehicles' positions and the cab's speed gradually transition
throughout a range of continuous values over time.. This makes taxi driving a continuous-
state and continuous-time problem. Driving a cab is an ongoing activity as well.
Local Lookup in Linear Spaces
Determinism (4.3): the nondeterministic condition is deterministic if the next state of the
environment is entirely deterministic, determined by the current state and the action carried
out by the agent(s); otherwise, it is nondeterministic. However, the environment may appear
nondeterministic if it is just partially observable.
Utilizing Nondeterministic Actions in
The unpredictable vacuum universe AND–OR trees
Observability (4.4): The environment is consider fully observable if an agent sensor send it
with access to the all-state of the situation at any given time. Parts of state may be missed
from the sensor data which creates noisy and faulty sensor may make an environment
partially observable. The surroundings is unobservable if the agent is equipped with no
sensors at all.
Investigating in Only Partially Observable Situations
looking but not making any observations
ing in situations that are only partially visible
Resolving issues that are partially observable
An agent in situations with partial observability
Local and Optimization Problems:
Without recording the paths taken or the collection of states that have been visited, local
algorithms work by sifting through states that are close to the starting point.
Not methodical; they might never go at a part of the area that really contains a solution.
Benefits: (1) they consume very little memory; (2) they frequently locate workable solutions
in expansive or limitless state regions.
Additionally, local algorithms can resolve optimization issues such as determining the
optimal state based on an objective function.
The purpose of local
Every state or point in the landscape has a "elevation," which is determined by the objective
function's value.
The goal is locate the high peak, or global high, if elevation matches an objective function
(Hill Climbing)
The goal is to locate the lowest valley, or global minimum, if elevation and cost are
correlated (Gradient Descent.)
Local algorithms:
Local algorithms often only travel to that node's neighbors and use a single current (as
opposed to several pathways).
Local and global : Local looks for paths from a starting point, whereas global , whether
informed or not, does the [Link] issues In observable, predictable, and well-known
environments, local consumes extremely little memory and produces reasonable results in
state spaces that are larger or infinite (continuous), making global inappropriate.
When attempting to determine the best approximation of a "objective function," such as the
reproductive fitness of natural populations as determined by Darwinian evolution, local can
be helpful.
Generic algorithms,
simulated annealing,
hill-climbing (greedy local ) and local methods
Consideration of state space landscape and gradient descent is helpful.
Hill Climbing: It maintains track of a single state at a time and, for each loop, advances to
the closest state with the highest value
Move your head in the direction of the steepest climb
stops when it reaches a "peak" in which no neighbor's value is higher.
Climbing hills does not look farther than the state's immediate neighbors.
Local maxima: A peak that is lower than the global maximum but higher than all of its
nearby states is called a local maximum. When hill-climbing algorithms approach a local
maximum, they will be pulled in the direction of the top, where they will become stuck
because there is nowhere else to go.
Ridges: When there are ridges, local maxima form a sequence that is exceedingly challenging
to greedy approache to traverse.
A plateau is a level section of state-space terrain. It may be a shoulder from which progress
is Shoulder possible, or it may be a local maximum flat from which there is no upward
departure.
Wandering around the plateau can cause a hill-climbing er to become lost.
The answer is to press on when we hit a plateau, allowing for a slight deviation in the hopes
that the plateau is actually a shoulder.
However, if we are in fact at a flat local maximum, then this strategy will continue to ramble
on the plateau.
Variants of Hill Climbing:
The likelihood of selection varies depending on how steep the uphill move is;
Stochastic hill climbing is implemented via first-choice hill climbing, which generates
successors at random until one that outperforms the present state.
Random-restart hill climbing follows this proverb. "Try again if you don't succeed the first
time." From randomly generated initial states, it es like a hill climber until it finds the goal.
The state-space landscape's form is a major determinant of hill climbing success: in the
absence of many local maxima and plateaus, random-restart hill climbing will rapidly
discover a workable solution.
Simulated Annealing:
A method for combining a random walk with hill climbing that produces results that are both
thorough and efficient
Annealing is the process in metallurgy that allows materials to get at a crystalline state with
little energy
heating them a high humidity and then progressively cools them. This helps to temperature
or hard metals and glass.
The simulated-annealing solution involvesvigorous shaking at a high temperature initially,
followed by a progressive reduction in shaking intensity (i.e., a drop in temperature).
But it selects a move at random rather than the optimum move. It is always acceptable to
make a change if it makes things better.
The "badness" of the move—that is, the amount ∆E by which the assessment is worsened—
causes likelihood to decline exponentially.
The move is accepted by the algorithm with a probability of less than 1.
A feature of the Boltzmann distribution, e-∆E/T, is that all the probability is concentrated on
the global maxima, which the algorithm will find with probability approaching 1, if the
schedule decreases T to 0 slowly enough.
to resolve issues with VLSI layout
Scheduling factories and other extensive optimization tasks
Local beam algorithm:
Rather than tracking only one state, the local beam method tracks k states.
There are k randomly created states at the start.
Every generates every one of the k states' successors.
The algorithm breaks if any one of them is a goal.
If not, it repeats after choosing the top k successors from the entire list.
Initially, it can appear that a local beam with k states is just a simultaneous execution of k
random restarts rather than a sequential one.
Every process in a random-restart operates separately from the other threads. the others
information is shared amongst concurrent threads in a local beam .
"Come over there, grass is green!" is effectively what the states that produce the best
successors tell the rest.
The algorithm promptly stops pursuing fruitless es and directs its attention to the areas where
the greatest advancements are being made.
Not having of variation among the k states can cause local beam to becomes focused on a
narrow state space area, thus turning it into a k-times slower version of hill climbing.
This issue is mitigated by a variation known as stochastic beam , which is comparable to
stochastic hill climbing.
Stochastic beam increases diversity by selecting successors with a probability proportional to
the successor's value, as opposed to selecting the top k successors.
Evolutionary algorithms:
Genetic Algorithms: Recombination is the process by which the fittest (highest value)
individuals in a population of individuals (states) create offspring (successor states) that make
up the following generation.
The population's size
DNA is a string over the alphabet, much as Evolution strategies ACGT In genetic
programming,
an individual is a computer program, while in evolution strategies, an individual is a sequence
of real numbers.
ρ is the number of parents that combine to generate an offspring;
ρ=1 (asexual), ρ=2, and ρ>2 (ideal for computing).
Selection: The procedure used to choose the people who will raise the next generation of
parents. Among all candidates, a selection method that is proportionate to each person's
fitness score is one option.
An alternative approach would be to choose n people at random (n > ρ), and then choose the
ρ most suitable people to be parents.
In the recombination process, a typical method (given ρ = 2) is to choose the crossover point
at random. choose a crossing point to divide each parent string into two, then rejoin the pieces
to create the two children.
The frequency with which children experience random alterations to their representation is
determined by the mutation rate. Every bit in an offspring's mixing is flipped with a
probability equals to rate of the mutation once it has been formed.
Elitism: The characteristics of the coming generation. This may consist just of the recently
created children, or it could consist of a few parents that scored highly in the prior generation
(a process known as elitism, which ensures total fitness never decline high time).
Evolution and Search
Charles Darwin formulated the theory of evolution in On the Origin of Species by Means of
Natural Selection (1859).
Key idea: differences in reproduction happen and are maintained in the next generation
roughly in reproductive fitness to proportion to impact.
Game Theory :
General Games: Agents in general games have independent utilities, or values based
on results.
It is possible to engage in competition, apathy, cooperation, and more.
AI shouldn't operate in a vacuum; rather, it should a) coexist with people and b) enhance their
lives.
This implies that each AI agent must complete a game.
Zero-Sum Activities : The utility of the agents are opposing (values on outcomes)
Consider a single value that both of them maximizes and minimizes.
Pure, adversarial rivalry
Zero-Sum Activities:
Checkers: The first computer player was born in 1950. 1994: The first computer champion,
Chinook, used a full 8-piece endgame to end the 40-year reign of the human champion,
Marion Tinsley. 2007: The solution to the checkers puzzle!
In a six-game encounter, Deep Blue defeats human champion Gary Kasparov in the 1997
Chess tournament. Deep Blue scanned 200 million places per second, utilizing highly
advanced evaluation techniques and proprietary technologies to stretch certain lines up to 40
ply. Though less historic, the current programs are far better.
Go: While machines are beginning to pose a threat to human champions, the greatest humans
are still able to defeat the most advanced machines. Go, b > 300! Traditional systems use
pattern knowledge bases, but the most significant recent developments use (randomized)
Monte Carlo expansion techniques.
Game Theory:
Game theory examines situations in which several parties, or agents, each have unique
preferences and possible courses of action. Each agent's utility is contingent upon the actions
of all other agents.
An agent's optimal behavior is contingent upon the actions of other agents.
incredibly cyclical!
Useful for both acting and predicting other agents' conduct, game theory investigates how
actors can logically acquire views concerning what other agents will do and, consequently,
how agents should act.
"Zero-sum" refers to the idea that there is no "win-win" result—what is advantageous for one
player is also detrimental to the other.
In games, where the vertices are states, the edges are moves, and a state may be reached by
more than one path, we frequently use the terms move and position to refer to "action" and
"state," respectively.
To decide which to make, we can overlay a portion of that graph with a tree.
A tree that tracks each move combination until it reaches a terminal state is what we refer to
as the entire game tree.
If the state space is limitless or if the game's rules let positions to repeat indefinitely, the
game tree could be infinite.
Optimal Decisions in Games:
MAX is looking for a series of s that will result in victory.
This implies that MAX's approach needs to be a conditional plan, or a contingent strategy
that outlines a course of action for every potential move made by MIN.
We require minimax , a slightly more broad algorithm, for games with multiple outcome
scores.
The best course of action for a given game tree can be found by calculating the minimax
value of each state in the tree, which we denote as MINIMAX(s).
Illustrating that all players play as optimal as possible from that point until game's
conclusion, the minimax value is the utility (for MAX) of being in that condition.
A terminal state's utility is its minimax value.
When it comes to moving in a nonterminal state, MIN chooses a state of minimum value (that
is, minimum value for MIN and maximum value for MAX), while MAX wants to move to a
state of maximum value.
The MiniMax Algorithm:
Optimal decisions in multiplayer games:
Initially, each node's single value must be changed to avector values.
Each node in the player game has a vector attached to it.
The vector provides the use of the state for terminal states from the perspective of each actor.
Implementing this as simply as possible involves having the UTILITY function returns vector
utilities.
Alpha–Beta Pruning:
While there is no solution that can totally remove the exponential tree, we can occasionally
prune it such that it only takes half the time to calculate the correct minimax instead of looks
at every state.
Pruning is the process of removing portions of the tree that you decide are unnecessary to
look at.
We also removed a significant portions of the tree when we looked at .
Continue
alpha is the value of player 1's best option thus far along the journey.
Beta is the value of player 2's best option thus far along the journey.
The overarching idea is this
Imagine there is a node n in the tree, and the player can choose to move to n.
Player will never go to n if Player has a better option at the same level (m ′ in Figure) or at
any higher point in the tree (e.g., m in Figure).
Benefits of alpha-beta pruning:
If pruning isn't done, O(bm) nodes must be examined.
Depending on which nodes we prioritize when cutting
If a random successor is selected, O(b3m/4) nodes must be examined.
We will need to look at O(bm/2) nodes if we are successful in selecting the best successor
first.
Useful heuristics to choose the next successor to take into account come very close to this
able to see twice as deeply as before!
What separates expert skill from reasonable play.
Monte Carlo Tree (MCTS) :
Alpha-beta tree has two main drawbacks: (1) it can only be used for four or five ply due to
branching factors; (2) it is challenging to create an appropriate evaluation function since
material value is not a reliable indicator and most locations are unstable until the finale;
Heuristic evaluation functions are not used in the fundamental MCTS technique.
Rather, the average utility over several simulations of whole games that begin at the state is
used to determine the value of a state.
A simulation, also known as a playout or rollout, alternates between selecting movements for
each player first and then the other, repeating the process until a terminal position is reached.
How should I play if both players choose at random?
That is the same response as "what is the best move if both players play well?" for certain
straightforward games, but it is not for the majority of games.
In order to obtain meaningful insights from the playout, it is necessary to implement a
playout policy that favors positive moves.
Neural networks have proven successful in learning playout policies from self-play for games
like Go. Game-specific heuristics, such "take the corner square" in Othello or "consider
capture moves" in chess, are occasionally employed.
After determining a playout policy, we must choose between two options:
What positions do we begin the playouts from?
For each position, how many playouts are allotted?
To find the move with the highest victory % from the current position, one can perform N
simulations using pure Monte Carlo , beginning from the current state of the game.
a selection strategy that concentrates computing power on the most crucial segments of the
game tree
states with few playouts and those that have performed well in previous playouts are
investigated to provide a more precise assessment of their worth.a selection strategy that
concentrates computing power on the most crucial segments of the game tree
states with few playouts and those that have performed well in previous playouts are
investigated to provide a more precise assessment of their worth
Selection: Using the selection policy as a guide, we begin at the tree's root and select a move
that leads to a successor node. We then continue this procedure, going down the tree until we
reach a leaf.
Choosing the move with the highest win percentage is an example of exploitation.
Exploration is choosing a node with a lower win percentage.
Expansion: We create a new child of the chosen node in order to expand the tree;
Simulation: Using the recently created child node as a starting point, we play out, selecting
moves for each player in accordance with the playout rules.
Back-propagation: Using the simulation's outcome, we now update each tree node all the
way up to the root.
Black nodes are increased in the number of playouts and wins because they prevailed in the
playout; as a result, 27/35 becomes 28/36 and 60/79 becomes 61/80. The white nodes are
merely increased in the number of playouts because they lost; thus, 16/53 becomes 16/54, and
the root 37/100 becomes 37/101.
Benefits:
In games like Go, when the branching factor is high and alpha-beta cannot deeply enough, or
when defining an appropriate evaluation function is challenging, Monte Carlo offers an
advantage over alpha-beta .
Given that the opponent will be attempting to reduce the score, alpha-beta selects the path to
a node with the highest possible evaluation function score.
Alpha-beta may incorrectly select (or forego) a path to a node as a result of a computation
error on a single node. However, Monte Carlo is less susceptible to a single mistake because
it depends on the total of numerous playouts.
Cons:
When it is likely that a single move would decide the outcome of the game, Monte Carlo has
an advantage because of its stochastic character, which makes it possible that it won't take
that move into account and won't even investigate a crucial line of play.
Unable to identify game states when it will take several turns in a playout to confirm the
result, but where it is "obviously" a win for one side or the other (based on human knowledge
and an evaluation function).