GSoC 2018 - Maria Ioanna Spyrakou

[MariannaSpyrakou]

Project: Finish aima-code algorithms and add explanatory notebooks.

Contributions: Finished planning (chapter 10-11) and knowledge in learning (chapter 19).

Work Accomplished:

Chapter 10-11, Planning:

• Implemented angelic search algorithm.
  Angelic search is a hierarchical planning algorithm that uses angelic semantics to identify and commit to high-level plans that work while avoiding high-level plans that don’t. Some key aspects of the implementation are:

  • Extended the HLA class into Angelic_HLA class, in order to add variables for the optimistic and pessimistic description of the HLA.
    • Extended the Node class (from search.py) in order to create a search tree that supports angelic HLA's.
  • Created the function angelic_action, that given an angelic HLA it returns it corresponding non-angelic HLA’s.
    • Created the functions reach_opt and reach_opt, that calculate the optimistic and pessimistic reachable set of a sequence of angelic actions.
    • Created the function decompose, which decomposes the original problem into subproblems. The initial state and goal for each subproblem are obtained by regressing a guaranteed-reachable goal state.
  • Added unit tests for angelic search and its auxiliary functions in tests_planning.py.

• Created iPython notebook for angelic search that contains:

  • Explanation of the implementation of angelic_search algorithm.
  • Examples that create a search tree of depth 2 & 3 .
    

• Implemented hierarchical search algorithm.
  Hierarchical Search is a Breadth First Search implementation of Hierarchical Forward Planning Search. Some key aspects of the implementation are:

  • Use the data structure Node from search.py in order to represent the search tree.
  • Modified refinements function so that it works for HLA’s with multiple refinements.

• Added unit tests for hierarchical search and its auxiliary functions in tests_planning.py.

• Created iPython notebook for hierarchical search that contains:

  • Explanation of the implementation of angelic_search algorithm.
  • Examples that create a search tree of depth 2 & 3 .

• Created separate notebooks for planning algorithms:

  • GraphPlan
  • Partial Order
  • Total Order Planner

Chapter 19: Knowledge in Learning:

• Modified the code for the FOIL algorithm (First Order Inductive learner).
  • Gain function was embedded inside choose_literal function. Since it is quite an important function for FOIL, I changed it into a seperate function that has its own unit test in test_knowledge.py.
  • I added an if statement inside new_literals function, in order to prevent picking a literal that is already in the current clause.
  • Added comments and improved readability of the code.
• Added unit tests for FOIL, more precisely added tests for the functions:
  • tell()
  • new_clause()
  • gain()
  • update_examples()
• Created iPython notebook for FOIL algorithm, that contains:
  • Explanation of the implementation of FOIL algorithm.
  • Examples that return rules for the family relations parent(x,y) and grandparent(x,y).
  • Examples that return recursive rules, such as for the family relation ancestor(x,y) and for graph connectivity, were tested, but did not return recursive result.
• Created separate notebooks for:
  • Current best
  • Version space

Experience:

At the beginning of GSoC I didn’t make a lot of progress, because I had troubles understanding some aspects of angelic search algorithm, and I didn’t ask my mentor, because I thought that my questions were too easy to answer and that I could manage on my own. Then, my mentor suggested to have hangouts calls once/twice a week. This was very helpful for me and critical for the projects progress, since I could address directly my questions, receive an answer and ask about some problems that I was facing with my code.

The “easy” part of the project was to implement hierarchical search, after having implemented angelic search, since angelic search is hierarchical search using angelic semantics. Furthermore, the existing implementation of FOIL algorithm was very well implemented, so it was easy to go through the code, understand every detail and work on it.

The most challenging part was implementing angelic search algorithm, since it wasn’t completely clear for me how to implement some aspects of the algorithm and how initial plan would be represented and what it should contain. Since initial plan is a key element of the algorithm, it affects almost all functions of the implementation, hence it was very time consuming to adjust any change of initial plan in the rest of the code. Another challenging part was to fit the code into the preexisting code, using the same structures and extending them in an appropriate way.

Some notes for future contributions:

• About Angelic search (chapter 11.3) there could be done a more efficient representation of the optimistic and pessimistic reachable set.

• About FOIL algorithm (19.5) it can be modified so that it can return a recursive set of rules. (More precisely, FOIL is calculating the utility of literals that refer to the target literal, but based on its current definition and not recursively.)

• Finally hierarchical search, angelic search and FOIL were tests in small instances, so it would be nice to test them in larger instances.

[antmarakis]

Great work, well done!

Just a heads up, in the 'Experience' section you cut off the second paragraph abruptly, and the third and fourth paragraph are not separated by an empty line.

Congratulations, once again!

[MariannaSpyrakou]

Thank you very much!

[amartya-k]

Wow

[delaray]

This is awesome Marianna, you did a great job. I think you chose a good level of granualarity. Thank you for adding the experience and future contributions sections. These will be especially useful to other aima-python contributors as well as future GSOC applicants.

[heisenbuug]

@MariannaSpyrakou I want to continue your work in GSoC 2019, can you suggest me a specific topic or place to start my work? It would be very helpful.

[rajatjain1997]

@MrDupin Can I take up the angelic search efficiency issue and the FOIL recursive set?

[heisenbuug]

@MrDupin I want to start working, can you guide from where I can start or rather from where shall I continue.