//****************************************************************************//
//******* Generate and Test / Means-End Analysis - September 6th, 2019 ******//
//**************************************************************************//

- So, we briefly mentioned genetic algorithms yesterday; let's look at an example of this in action with - you guessed it - a YouTube video!
    - *cue video optimizing traveling salesman problem w/ GA*
    - Mainstream AI apparently has moved away from genetic algorithms, with very few papers published on it - why haven't they been accepted?
        - It seems that the completely random process of creating solutions / mutating solutions leads to very slow convergence, and discourages researchers from pursuing it - it seems we have a LOUSY generator that doesn't take any advantage of what it knows about the world
        - It also has the problem of needing to define a FITNESS FUNCTION - but for most problems, it's very difficult to find a good fitness function that works in all cases!
            - "This is one of the dangers of applying semi-scientific ideas from science to human societies, like with eugenics; people have had very misguided ideas about what a 'fit' society looks like"
            - At the same time, the tester is EXCELLENT, but is difficult to actually create for most problems

- Here's an example problem that you can do generate-and-testing on: starfish are dying in coastlines across the United States. Why?
    - Rising ocean temperatures? Pollution? Increased ocean acidification? Death of their favorite prey types?
        - We don't know which of these options is right, but all of these sound like REASONABLE ideas - no one said they're dying because of stock market fluctuations! We did a good job generating things!
    - At the same time, how do we test these ideas to eliminate the less plausible ones? Maybe we can look at historical temperature data, or do surveys on current starfish prey populations...
        - Perhaps one of the key facets of human intelligence is that we're very good at making reasonable generations and coming up with reasonable tests - although we're certainly not perfect
            - "Almost all human tasks have generators and testers that aren't lousy, but also aren't perfect"
        - In general, we generate enough ideas to test them out, but not so many we can't sort them all out
            - One problem with many Georgia Tech classes: we often teach you to find THE solution to a problem, but most problems have many different possible approaches, and it often isn't clear which one is best ahead of time
--------------------------------------------------------------------------------

- One thing we should note is that knowledge representations and problem-solving techniques are closely related

- This sort of generate-and-testing technique we've been doing is what's known as an "informed search"
    - BFS and DFS are uninformed searches; they just exhaustively search through all possibilities
    - Pruning our options with generate-and-test techniques, though, allows us to speed up the search by only looking at promising options - at the risk of ignoring actually good options our algorithm didn't realize were promising
        - "Almost all interesting problems in the world, and especially in AI, are intractable"
    - Why do we go to school? Purely practically, Professor Goel think it helps us in 2 main ways:
        - To learn about already solved problems, allowing us to decompose problems into pieces we already know how to solve, letting us solve them more quickly
        - To learn heuristics and rules of thumb, that allow us to get decent solutions in a reasonable amount of time
            - Similarly, knowledge plays these 2 roles in KBAI

- We can apply generate-and-test to Raven's matrices, too
    - For the particular problem on the slide, though, there are 2 different ways we could do generate and test:
        - Find the relationship between A/B, apply it to C/D, and then check what's changed and go through all the answer options and pick the closest match
        - OR, they'll look at all the answer options (1 - 6), and for each answer they'll compare it with A/B and C/D, and choose the answer that best fits both A/B and C/D
    - People use both of these strategies, and while different people usually have a preference for one or the other, we can all use both of them if we need to
        - In fact, humans are amazing: if one of these strategies is struggling, they'll SWITCH and use the other one! That requires METACOGNITION, and realizing our current strategy isn't working - that's incredible!
        - So, should we build an AI to use one of these strategies? Which one? If we want them to use both, how can we implement metacognition (which is notoriously difficult)?
    - For Raven Matrix problems in particular, machine learning techniques, Markov Decision Problems, and so on have been tried and haven't worked very well - why?
        - Because these problems are dependant on understanding relationships - and that's not what those AI approaches were designed for

- Alright, I think that covers the basics of generate-and-test for now

- Now, we're going to keep diving into problem-solving techniques with MEANS-END ANALYSIS
    - What's that? Well, imagine there's a toddler in your family, and you give the child a set of 3 blocks labeled "A", "B", "C", like so:

                C
                A   B
            ------------

    - We then want them to move the blocks into the following pattern by ONLY 1) moving one block at a time, and 2) only moving blocks with no blocks above them:

                A
                B
                C
            ------------

    - This seems like a trivial problem (and it is), but many toddlers struggle to solve it! Animals can't solve it! Why?
        - 

- So, MEANS-END ANALYSIS basically means that we'll write down a list of "operators" that we can use to solve a problem, and which ones are currently available
    - So, we might know we have the "Move(block, location)" operator, and that the current STATE of the world is:
            - A on Table
            - B on Table
            - C on A
        - Therefore, the current available moves are:
            - Move(C, Table)
            - Move(B, Table)
            - Move(C, B)
        - "One operator us adults forget about here is 'Cry', which is very effective because mommy and daddy come and fix the problem for you"
            - How do we figure out what operators are available? That's an excellent problem, but one we'll defer for the moment; we're just talking about what we need to learn in the first place
    - Importantly, we ALSO know what our GOAL STATE is:
        - A on B
        - B on C
        - C on Table
    - So, we want to figure out how far away our current state is from our goal, and then pick an operator that'll get us closer! THAT'S how we solve this problem, and avoid resorting to "Cry"!

- Alright, we'll dig further into this topic on Monday - goodbye!