Fichas
361 - Artificial Intelligence
Fichas del conjunto (158)
- 1What is Turing original imitation game?3 roles: interrogator, assisting agent and deceptive agent
Req: interrogator work out which agent is male and which is female - 2What is the modern Turing test?Interviewer vs agent
determine if agent is human or computer - 3What is the name of the objection example of the modern Turing testSearle's chinese room
- 4Describe the principle of Searle's Chinese roomIf a prisoner was in Chinese prison and based signs.
If provided rules, he could pass back replies (or signs) but that doesn't mean he understands what questions were asked or even his own replies. - 5What are the counter arguments (replies) to the chinese roomsystem reply - Searle doesn't understand, but the room as a whole does
Robot reply - what is missing is a grounding of the symbols to real-world objects
Brain simulator reply - rule matching program actually represents neural firing - 6What are the objections to the Turing test?measure only one aspect of intelligence: communication ability
it only capable of measuring intelligence based on human language related communication e.g. language specific and doesn't test animal intelligence - 7Name some problems that are easy for humans but hard for computersrecognising objects and understanding images
walking - 8name some problems that are easy for computers but hard for humansstoring and repetitively analysing large amounts of data
production factories - 9What is human computation?combines the strength of humans and computers.
For example, if its easier for humans, let the human do it otherwise the computer will - 10what are examples of human computation tasks?CAPTCHA (Completely Automated Public Turing Test to tell Computers and Humans Apart)
reCAPCHA
ESP Game - 11What are the tasks for CAPTCHA, RECAPTCHA and ESP GamesCAPTCHA - an image has distorted text or a picture which must be labelled.
Easy as a human to do but hard as a computer
ReCAPCHA - similar but helps translate text
ESP GAME - label images - 12How do we do problem formulation/what make up problem formulation?A well defined problem
-known initial state
- a set of possible actions/operations
State space: the set of all states that are reachable from an initial state by any sequence of actions
Path: sequence of actions leading from one state to the next - 13What is the Queen problem?Place a queen on any open square and repeat till all 8 are placed but in positions where no 2 queens can attack each other (e.g. same column, row or diagonal)
- 14Describe the 3 formulations of the Queen problemFormulation 1: place queen on any open square, repeating until all queens placed
Formulation 2: placing each queen on its own row
formualtion 3: placing first queen on row 1, then next queen on next row and different column, repeating till all placed - 15What are the measurements of performance when it comes to basic search?Completeness: is this strategy guaranteed to find a solution if one exists
Time complexity: how long does it take to find a solution
Space complexity: how much memory does it require to perform the search?
Optimality: does the strategy find the best-quality solution when more than one exists - 16Describe what Breadth first search does. (essentially benefits included)Finds the most shallow solution
It is complete (finds best solution)
Optimal when the path cost is a non‐decreasing function of depth
Tijan note: does each level at a time - 17What are the problems with breadth first search?Requires lots of time and space
Exponential growth leads to impractical problems for uninformed search - 18Describe what Uniform cost searchcost associated with each link
go to nodes with lowest cost
always start at start state (add the costs of each node you have to go through) - 19Describe depth first Search. Including it pros and consYou completely explore one path, then pop back one, explore other branches, repeating till done full tree
Non-optimal
trees with infinite depth, depth-completeness sacrificed - 20Describe depth limited search. What are its requirements, pros and conscompletely explore a branch until at the depth limit, go back 1 and explore the other branches doing the same, repeating
Requires some knowledge of solution
non-optimal
limit too small-sacrifices compeleteness - 21Describe iterative deepeningtries all possible depth limits in turn (1,2,etc)
there a cost of re-computing the lower levels - 22What is Bi-directional search?Starting with solution and working backwards
Allows you to limit the search depth - 23What are Reflexive agents and what are goal based agents?Reflexive agents: fixed set of conditions -action rules. Unable to plan ahead
Goal based agents- consideration of future actions (more global). Problem solving agents: find sequence of actions that lead to a desired goal state when the problem is well defined - 24what are the types of blind search?breadth first search
depth first search
iterative deepening search
uniform cost search
depth limited search
bi-directional search - 25How can we improve blind search?avoid repeated states!
use caching to store the values of subtrees
-table of all visited states and the results
Change rules for generating the trees
- don't generate repeated states
do not generate paths with cycles - 26What is a heuristic function and it use?is an inexact estimate of the evaluation function
Used to describe how valuable each state is in obtaining the goal, so you choose to expand to node that has best value - 27What is best-first search?a search that relies on a heuristic function to determine which node to go to
Pick lowest costs first - 28What is Greedy search?minimise estimated cost to reach a goal
this is not optimal and not complete - 29What is A* search?combination of greedy search with uniform cost search
minimise total path cost (f) = actual path cost so far (g) + estimated of future path to goal (h) - 30What is the heuristic function requirement for A* searchadmissible - it must never overestimate the cost to the goal
so we usually use the distance between that node and the goal - 31What is the completeness of A* search?Complete when:
-finite branching factor
-every operator costs at least some positive
Incomplete when:
-there node with an infinite branching factor
- a path with a finite path cost but an infinite amount of nodes - 32What is the complexity of A* search?computation time is limited by heuristic function used
issue 1: choosing right heuristic function can heavily affect the complexity
issue 2: limit the memory requirement as all nodes need to be kept in memory - 33You have the 8 puzzle problem. Two heuristic options h1 = number of tiles in the wrong position h2 = sum of distances of the tiles from their goal position. Which is better and why?h2 is better
because you want to use heuristics with higher values, so long as they dont over-estimate - 34What are the techniques for memory bounded search?iterative deepening depth-first search
iterative deepening A* (IDA*) - 35How does iterative deepening depth first search work?run depth first search with increasing depth limits until goal is found
uses much less memory since at each iteration it does depth first search (so max num of nodes to be stored is equal to depth, or longest path that it explores) - 36How does iterative deepening A* search work? What is it's requirementeach iteration is a depth first search with a limit based on total path cost (f) rather than on depth
Space proportionate to the longest path that is explores - 37In A* search for motion planning, what is the input and output?input: start, goal, environment with obstacles, sometime a description of object that is moving
output: a path from start to goal that avoids obstacles - 38Iterative deepening A* search has a cutoff f (total path cost), what is it?at initial state: the estimate of the cost at that state
then threshold f used for the next iteration is: min cost of all values that exceed the current f threshold - 39What are the 2 main problem solving methods including their sub-methods1) Optimisation - some function to maximise or minimise under some constraint e.g. genetic algorithms
2) Classifications
2a) Unsupervised e.g. clustering
2b) supervised e.g. neural networks or decision trees - 40What kind of data is used in decision trees? What can they be used?continuous data can be split, dividing space and used to create decision trees
Decision trees can also represent a Boolean function - 41How do truth tables and decision trees work together?truth table row = path in tree from root to leaf
- 42What are the guidelines for making simple (small) decision trees?-test most important feature first
-if you have only one type example, return a leaf
-else, choose next most important feature
-if you run out of examples return a default feature (although we assume this won't happen) - 43How do we decide which attribute to split on for decision trees?a good attribute should reduce uncertainty. e.g. split the example subset so that they are ideally all positive or all negative
- 44what does entropy measure? When is entropy highest?the amount of uncertainty in a probability distribution
Entropy is highest when uncertainty is greatest - 45How do we find information gain?uncertainty before - uncertainty after
- 46How do we find information gain (IG) for attribute A?IG(A) = Entropy before - AvgEntropy after choosing A
- 47What is a learnt decision tree?a decision tree that is now simpler due to
creating smaller tree through information gains and entropy
To make you keep splitting attributes until leaf nodes are completely classified into one class - 48What is overfitting (decision trees)finding meaningless "regularities" in the data -e.g. every time i flip a coin with my left hand it comes out heads
Present due to noise in data, so some features have multiple examples with conflicting results - 49What are the limits of decision trees?don't have relevant features (missing data attributes)
attributes have too many possibilities (i.e. multi-valued attributes)
attributes is continuously valued
All cannot be handled (?) - 50What is probability theory, utility theory and decision theory?Probability theory describes what an agent should believe on the basis of evidence
Utility theory describes what an agent wants
Decision theory puts the two together to describe what an agent should do - 51What are the probability axioms0 ≤ P(A) ≤ 1
P(True) = 1
P(False) = 0
P(A B) = P(A) + P(B) – P(A B)
P(¬A) = 1 – P(A)
P(A B) = P(A|B) P(B) (the product rule) - 52Probability part 1 refresher
- 53What is bayes rule and the product rule?
- 54What makes up a belief network?nodes - random variables
arcs with arrows - showing direct influence
Probability of events for each node - 55What does the Conditional independence property look like and tell you?P(X | A, B, C…) = P(X | Parents(X))
where Parents(X) gives those nodes (A, B, etc.) that
are the parent nodes of X - 56What are the steps in creating a belief network1. choose the set of relevant variables
2. choose an ordering for the variables
3. while there are variables left:
a. pick a variable a1 and add a node to network for it
b. set parent(a1) to the minimal set of nodes that satifies the conditional independence propery
c. define the conditional probability table for node a1 - 57What's the "correct order" to add node to a belief networkadd node that is root cause first and then the variables they influence
order can make a difference in the number of links in the network - 58Where do the 3 types of probabilities come from?Frequentist - probabilities come from experiments. e.g. 9/10 people agree
Objectivists - probabilities are real aspects of the universe. Propensities of objects to act in certain ways
Subjectivists - probabilities characterise an agent beliefs. e.g. in my opinion... - 59How are genetic algorithms represented?in strings, e.g. numbers, letters, arrows etc
where there is one character per square - 60What is random selection (genetic algorithms)a random sequence is selected at each stage
No memory/history so each random selection is completely new
eventually something useful will result - 61What is the basic Genetic algorithm process?
- 62What are the ways of encoding a chromosome? (chromosome contain info about the solution they represent)Binary encoding
Permutation encoding
Value encoding
Tree encoding - 63What does binary encoding look like and mean?Square for each binary chromosome
each bit can represent some characteristic of the solution or whole string can represent a number
E.g. knapsack problem, each bit can be an item in the sack - 64What is permutation encoding look like? When is it useful?every chromosome is a string of numbers which represent a sequence.
E.g. travelling salesman, number in square = order the city is visited in
Useful for ordering problems - 65What does value encoding look like?Every chromosome is a string of values
values can be anything connected to problems
e.g. each square is a decimal number, letter, or arrow direction - 66What does Tree encoding look like? What's it main use?every chromosome is a tree of objects, such as a function or command in a programming language.
The tree was read like depth first in the example
use: evolving programs or expressions - 67How do you define a fitness function? (Genetic Algorithms)if correct answer known: fitness function is distance metric towards that answer
if unknown: estimate of the value of the solution - 68Why is it so important to have a good fitness function for genetic algorithms?Evolution can only be as good as the fitness
- 69What is the easiest selection process for genetic algorithms and why does it fail?easiest way is to pick the n most-fit individuals
Fails because now you lose all diversity and stuck in a local minima - 70What are the selection processes you can go through for genetic algorithms? Also what must be done to prevent loss of the best chromosomesroulette wheel selection
rank selection
Must do selection elitism: copy some of the best chromosomes to new population - 71Explain roulette wheel selectionParents are allocated space on the wheel in proportion to their fitness
Throw marble (spin wheel) and select the chromosome it falls on
Chromosome with largest fitness values will be selected more times - 72Explain rank selection. What does it fix?Every chromosome receives fitness from its ranking
-worse fitness assigned 1
-best assigned number of chromosome in population
Fixes issues when fitness varies greatly (so one chromosome would dominate in Roulette wheel)
Leads to slower convergence, as best chromosome don't differ too much from other - 73What kind of mutation can be done in binary encoding? Whats it benefit?bit conversion, swapping a random bit round. e.g. 1100 -> 1110
It prevents problems with local minima - 74What are the different types of crossover (Genetic algorithms)?Single point over
Two point crossover
uniform crossover
Arithmetic crossover - 75Explain single point and 2 point crossoverSingle point ->Splitting 2 chromosome in half to create 1 new one with each half of original
Two point -> similar to above but having 2 splits. e.g. first 2 bits and last 2 bits
Both don't require equal amounts from each parent. e.g. can split 75/25 - 76Describe uniform crossover and arithmetic crossoverUniform crossover is splitting the chromosome from each parent in half (although random points) so the offspring is exactly 50/50 of each parent
Arithmetic crossover is using an arithmetic operation (e.g. AND) - 77How do you preform mutation and crossover with permutation encoding?single point
-one crossover point is sselected, copy sequence before crossover from first parent, scan second parent for sequence of remaining. e.g. |>1234<| 678 + (453|>68<|2|>7<|) -> 12345678
Mutation is changing the ordering, two number swap places - 78How do you crossover and mutation with value encoding?crossover- same as normal crossovers e.g. single point, 2 point etc
mutation differ depending on what used
-real number: add/subtract a small value
alphabet symbol: advance one place A->B
direction: rotate clockwise - 79How is crossover and mutation done with tree encoding?crossover: swap an arc around. doesn't need to be same arcs (all thing attached go too)
mutation: change a child node - 80What are the replacement strategies for Genetic algorithmsSteady‐State Selection
– In every generation, select a few high fitness
chromosomes for creating new offspring
– Remove some low fitness chromosomes
– Replace these with new offspring
– Remainder of population remains Generational Selection
– All population members are removed on each
generation - 81What are the parameters of a Genetic Algorithmpopulation size
encoding choice
crossover probability
mutation probability
replacement strategy
fitness function - 82What are the advantages and disadvantages of Genetic algorithmsadv: parallelism, relatively easy to implement, less likely to get stuck in local extrema
Dis: choosing encoding and fitness function can be hard, computation time, no solution found guarantees, strong dependance on parameters - 83What are iterative improvement algorithmswhen you start with complete configuration and then make modifications to improve quality
e.g. 8 queen problems. start with all queens on board and then shift them around until a solution is achieved - 84What happens during Hill-Climbing search?you move in the direction of increasing value within a local area of the state space
You don't maintain a tree (no reconstruction of path through state space) - 85What the problem with Hill-Climbing search?local maxima/minima
- 86What do minimax search assume? What's its issues?Assumes opponent asks exactly as you would and cannot look ahead
Its impractical to build a full tree
partial trees require a heuristic function and limit depth which can impact the tree - 87What can evaluation function account for in minimax search?positioning, turns, board positions
- 88What is the principal of alpha beta pruning?if you have an idea that is surely bad, don't take time to see how bad it really is
- 89How do minimax trees include chance in the results?It treats chance as another player
nodes determined by chance, compute expected values on the probability distribution - 90What is the inputs for path planning? (motion planning)geometry of robots and obstacles
kinematics of robots (degree of freedom)
start and goal positions - 91What is path planning goals in motion planning?computing a collision free path for rigid or articulated object (the robot)
moving from start position to goal position while avoiding obstacles - 92What are the path planning outputs for motion planning?Continuous sequence of collision free robot configurations connecting the initial and goal configurations
- 93Explain why path to endpoint is insufficient when motion planning with an articulated robot armbecause it doesn't tell us how to move individual joints
- 94What is NLP?Natural language processing. e.g. English
How to train system to understand language - 95What is the philosophy of machine intelligence?Raises important ethical and legal questions
e.g. who is responsible for the machine
emotions
social - AI in clinical situation - 96Why do we need NLP?HCI: Natural language interfaces for users
+ natural form of communication
- inefficient for expert users, less precise
Information/knowledge management
- Summarisation
- Search engines
Study and description of language
- Linguistics
- Lexicography - 97What makes it hard for computers to understand natural language?Ambiguity - things can have multiple meaning or contexts
- 98What are the types of ambiguity?Pragmatic - meaning in context
Semantic - meaning in sentence
Anaphoric - referential. What/who does each pronoun refer to
Syntactical - structure/grammar. how does the words fit together in the sentence?
Lexical ambiguity - word level. words can have more than one meaning - 99What is Metonymy and metaphors? (literal and figurative ambiguity)Metonymy - one object stands for another e.g. Citreon announced new car. Citreon stands for the rep of the company
Metaphor - figure of speech where something that can't do something, does something. e.g. prices have fallen (can't literally fall) - 100What are the levels of annotation (NLP processors?Orthographic - interpretation of italics, initial capital letters or the full stop. delimitation of words by space
Phonological - syllable boundaries
Phonetic or Phonemic - phonetic / phonemic segments: consonants and vowels
Morphological -prefixes, suffixes and stems - 101What are the Principals of POS tagging?1. rule based tagger
2. Probablistic tagger - 102What is rule based tagging?Step1 : apply most likely tag for each word
step 2: improve result by iteratively applying set of patch rules
-e.g. look at word before and after to deduce meaning
Correct patches are added to lists in order of success - 103What is probabilistic POS tagging?If words have multiple tags, we choose the most likely sequence of tags by calculating the probability of all possible sequences of and choosing the highest probability
- 104What is Unigrams, Bigrams and TrigramsUnigrams - tags one word
Bigrams - tags pairs of words
Trigrams - tags triplets of words - 105what is First order HMM and Second order HMM?First order HMM - estimates used for tag transition probabilities from bigrams
Second order HMM estimates for tag transitions probabilities from trigrams - 106Whats the accuracy for probabilistic, rule based and hybrid taggers?rule based - 90%
probablistic 95-96%
hybrid is 97-98% - 107What is the Claws POS tagger?a hybrid tagger that uses hidden Markar Model (HMM) and rule based techniques
used to POS tag 100 million word british national corpus - 108What is the Claws POS tagger good and bad for?robust across speech and writing but struggles with poetry
- 109What is the process for Claws POS tagging1 Tokenisation - segmentation of text into words and sentences
2 Initial POS tag assignment - lexicon suffix list and heuristics for unknown items
3 Contextual disambiguation - rule based
4 Contextual disambiguation - probabilistic (HMM)
5 Contextual Disambiguation - rule based - 110What are the different views of language and meaning?1. language as a communication system
-in NLP need to automate the process of mapping/translating the linguistic forms into meanings
2. language as a sign system
-In NLP, we need to automatically break language data into appropriate linguistic sign units and associate them with correct meanings - 111What are the 4 kinds of semantic study?Lexical semantics - study of the meaning of linguistics lexical units. e.g. single words, idioms, set phrases
Pragmatic semantics - meaning of language in context
Grammatical semantics - study meaning of words which have relevance to grammatical role or syntax
Logical semantics - study relations between natural language and formal logical systems - mainly focusing on meaning (proposition) of sentences - 112There are different language meanings in units for NLP, what are Morphological and lexical units?morphological unit (morpheme) - minimal meaningful unit of a language; including simple words and sub words unit such as prefixes and suffixies
Lexical unit - a single word, or part of a word, or a chain of words.e.g. "computer" or take care of - 113There are different language meanings in units for NLP, what are Syntactic (constituent) and larger units units?Syntactical units a word or group of words (phrase or clause) that function as a single unit within a sentence hierarchical structure e.g. subject, predicate
Larger units are things such as paragraphs,sections and documents - 114What are the types of language meaning in units?morphological unit (morpheme)
lexical unit
syntactical unit
larger units
Multi word expression - 115Why are multiword expressions an important lexical unit?In actually communication, a significant part of semantic information is conveyed in multi-word expressions
e.g. "kick the bucket" - 116What are the main causes of word sense ambiguity?Homophony: different words have same sound
Homonymy (Homograph): different words have same spelling
Polysemy: a word can have more than one sense
Figure of speech: a word or multi word expression used in a non-literal sense - 117What are the different word sense relations? (meanings)Synonym vs Atonym - similar or opposite relations
Hypernym or hyponym - is a relation. e.g. animal / dog
Meronym - part of relation. e.g. wheel meronym of car - 118What is wordnet?a major lexical resources organised by word sense relations
Used because its challenging to automatically determine sense relations - 119What is semantic annotation?the process of attaching semantic/meaning information to appropriate linguistic units in natural language data in a machine readable form
- 120Why do we do semantic annotation?1 - Machine readable, so can support automatic information analysis and management
2 - allows us to conduct language data analysis at higher abstraction lvls .e.g. collect text about food or car
3 - allows semantic analysis of multiple languages data without worrying about different writing systems - 121What are the ways to disambiguate word sense?rule based - rely on certain rules to select word sense
statistical methods - measure probability of word sense with given context features
hybrid - combines both approaches
Many methods rely on context information - context being the surround words or tags - 122What must you consider when designing a semantic tagger?accuracy/recall
speed
efficient accessibility
copyright
etc - 123What is a machine?a semi or fully automated device that magnifies human physical and/or mental capacities in performing one or more operations
- 124Broadly explain when a machine learns?when it changes its structure, program or data (based on its input or in response to external info) in such a manner that it expected future performance increases
- 125What did Tom Mitchel say about a computer program is said to learn?A computer program is said to learn from Experience (E) with respect to some Task (T) and some performance measure (P), improves with Experience (E)
- 126What are some of the applications of machine learning?speech recognition - Alexa, Siri
Face recognition - facebook tag a friend suggestion
Fraud detection - paypal
Travel shortest path - Google map
Recommendation - netflix, spotify - 127Machine learning is unlikely to replace every human job but what jobs has it been replacing at the moment?assembly line and factory work
vehicle drivers
phone operators, telemarketers, receptionist
bank tellers and clerks - 128What is the learning process begin with?Observations / data (examples, direct experience, instructions)
Finding patterns (those who buy cereal buy milk)
Make better decisions (place milk near cereal, but away from sea
food) - 129What is the aim of machine learning?to allow computers to learn (training) automatically without human intervention or assistance and adjust accordingly to make decision in future events (testing)
- 130Machine's learn algorithms learn from data, what do they try to learn?to find relationships, develop understanding, make decisions and evaluate their confidence from the data given
- 131Why is training data important to machine learning algorithmsthe quality and quantity of training data provides the means to build the model
it has has much to do with the success as the algorithm themselves - 132How do we test machine learning algorithms models that have been created from the training data?we give the trained model data that it has not seen before
Data sets are split up, some for training, some for testing. They are given on different random folds (called cross validation)
This stops overfitting - 133What is over-fitting? (Machine learning context)when your model fits with a particular training data but fails to fit additional data or predict future observations reliably
- 134What are the different types of machine learning algorithms? Examples for eachSupervised - Naive Bayes, Linear Regression
Unsupervised - Clustering K-means
Semi-supervised - a combination of both - 135What happens during supervised machine learning?Apply what is learned in the past to new data using labelled examples to predict future events
-expensive as usually human has to label examples
Starts from the analysis of a known training dataset - 136How do unsupervised machine learning algorithms work?the training data provided is unlabelled
studies how systems can infer a function to describe a hidden structure from unlabelled data - 137What happens during semi-supervised machine learningsome data is labelled and some is not
use it because labels is costly - 138What is a feature? (machine learning)? Why is it used?an individual or measurable property or characteristic of a phenomenon being observed
e.g. shape, colour, texture, taste, price, origin
MLA must be able to distinguish between helpful features and useless features - 139Why do we do feature reduction? (removing irrelevant features)irrelevant features can decrease accuracy of many models
improve accuracy - less misleading data means modelling accuracy improves
reduces over-fitting - less redundant features means less opportunity to make decisions based on noise
reduces training times - less data means the algorithms train faster - 140What is the training data requirements?how much data depends on:
task
performance to achieve
input features
noise in data
noise in features
complexity of models - 141What is text classification?text classification assign one or more classes to a document according to its documents
.e.g detecting spam (spam or not spam are classification) or detecting news article topics (politics, sports, science, ...) - 142What are features in textual data?verbs, nouns, pronounces
adverbs, functional words
word length
num of syllables
topics
word frequency
different word
syntax, semantics
readability - 143What is WEKA? What does it contain tools for?a collection of machine learning algorithms for data mining tasks
Tools for: data preprocessing, classifications, regressors, clustering and visualisation - 144What are ARFFs? (Attribute-Relation File Format)Used in WEKA - data sets must be converted into them
Structure format that contains comments, data set names, attributes, target/class variables and data values
Once ARFF converted, you can train the model using any supervised training algorithm - 145What are the methods for path planning in configuration space?probabilistic road maps
cell decomposition
visibility graphs
potential fields - 146What are the principals of probabilistic road maps-sample the configuration space at random
-keep samples in the free space
-connect pairs of samples by simplest path - 147What are the problems with Probablistic roadmaps?Sampling strategy is critical
Incomplete
– No guarantee of performance
– How fast does it converge?
•Still can be an effective tool for planning with many degrees of freedom - 148What do probabilistic roadmaps provide?provide an effective computational framework to plan motions with many degrees of freedoms
- 149What is a Visibility graphs? What are some vertices and edges?(create) a non-directed graph
Vertices include: start position, goal position, vertices of all C-space obstacles
Edges - straight line segments connecting all pairs of vertices that don't go through obstacles - 150In visibility graphs what does the shortest path look like?if path is not obscured, the shortest path is a straight line
If go to go around obstacles, the shortest path will be from one of the vertices
3D space - shortest path is straight line but if obstacles shortest path may be from an edge - 151What do Voronoi Diagrams consist of and what do they maximise? (skeletonisation method)consist of curves in C-space that are equidistant from one or more points in the blocked space
maximise free space between robot and obstacles - 152What is the process for cell decomposition: rasterisation?choose a pixel resolution
mark each pixel as blocked, partial blocked or free
only generate paths through free squares
(you can decompose partially blocked squares into smaller units) - called iterative cell decomposition - 153Whats the issue with rasterisation (cell decomposition)?it limits dimensionality (becomes a search problem)
its non-optimal - 154What is Cell Decomposition with Stripswhen you use non-square cells of variable sizes
any cell that shares an edge is adjacent
robot can navigate between adjacent cells by moving from one cell centre to the midpoint of the shared edge - 155Cylindrical Decomposition use critical points but what are they?points in configuration space where the boundary curve is
- 156What is potential fields?scalar function over the free space
ideal field is smooth, with a global minimum at the goal, no local minima and grows to infinity near obstacles - 157How do robots move across potential fields?robots move along the gradient
- 158whats the difficulty of potential fieldscomputing an ideal potential field is likely to be at least as hard as path planning
Información
- Descripción
- Computer Science Fichas sobre 361 - Artificial Intelligence, creado por Tijan Weir el 09/05/2018.
- Creado por
- Tijan Weir
- Visitas
- 4
- Valoración