% -*- Mode:TeX -*-
\documentclass{article}

\usepackage{sigcse2e}

\begin{document}

\title{Artificial Intelligence (W4701)\\
Homework 1\\
Search: Problems, Practicalities, and Palindromes       }

\author{
	Eric V. Siegel \\
	Computer Science Department \\
	Columbia University \\
	New York, NY 10027 \\
	evs@cs.columbia.edu
       }

\maketitle

\begin{abstract}

{\it SUN, a Java Janus.}

For this assignment, students implement standard search techniques and
explore heuristic measures of their own design for a palindrome
discovery system.  The system successfully derives palindromic
sequences of words, many of which are meaningful, and achieves what is
to the author's knowledge the first automatic deduction of
palindromes.  Code is made available to students which implements the
state space for palindrome search.

{\bf Due date: Oct. 5.}  However, you are encouraged
to do this by Sept. 30, since at that time
a 1.5 week assignment will be handed out.

\end{abstract}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Reading and Written Exercises}

\subsection{Reading}
Chapters 1 - 4 from Russel and Norvig (Section 4.3 is optional).
Also, you are responsible to read this paper to understand the state
space for palindrome search, even if you choose to do the alternative
search assignment.

For students who do not wish to program in Java, alternative
programming assignments are given at the end of this writeup, below.


\subsection{Written Work}

\begin{itemize}

\item
Exercises 3.1.

\item
Could bidirectional search be used for iterative improvement
problems such as n-queens, VLSI and palindrome creation?  If so, how?
If not, why not?

\item
For your favorite palindrome (created by anybody or anything), show a
possible (search) path (i.e., series) of operations that could have
derived it.  You'll want to read the rest of this paper before doing
this.

\item Exercises
4.4, 4.5, 4.6, 4.8.

\item Exercise
4.13 (parts a, b, c and d only -- no implementation required)

\item
Show a trace of A* search on the U2 puzzle, with the
heuristic simply being the value of the slowest person
who still needs to cross the bridge.  Assume
the search space is defined to only allow operations
that bring 2 people across the bridge towards
the destination, or one person back, always with the
flashlight.  To remind you of the problem: four
people need to get across the bridge, 2 at a time
at most, with a flashlight.  They take 1, 2, 5 and
10 minutes, respectively.  When two go together,
the go at the speed of the slower person.  This
can be done in 17 minutes.  Follow a link from
the course webpage to try out a demo.

\item
Describe why the U2 heuristic above is admissible.
Then, invent an admissible heuristic for the U2 puzzle
that is better.
In 2 or 3 sentences, provide an informal proof
that your heuristic is indeed the better of the two
(cf. the text for help on comparing heuristics).

\item 
{\it Read this question a few times in order to understand it -- it is
secretly a crash course in machine learning.}  Describe the initial
state, goal test, operators, a reasonable heuristic and a path cost
function (just 1 or 2 sentences each) for a system that searches for a
good rule to classify a person according to her or his gender,
nationality, hair color and eye color as to whether the person would
be allowed into the (fictional) Exclusive Styx Fanclub.  Assume you
have a database of people and whether or not they were accepted (and
your rule, developed from this data, will make a generalization about
type of person get's accepted).  Assume the rule is of the form ``If
eyecolor = blue and nationality = Canadian and gender = WILDCARD
(either gender accepted) and haircolor = green then
AcceptedAsMember''.  There are many ways to approach this problem, so
there are many acceptable formulations for the operators, etc.

\end{itemize}



\section{Introduction}

{\it Infinitesimal clam I set in Ifni.}

Search is
a fundamental concept, serving as the basis for a great portion
of advanced AI techniques such as planning, natural language
generation, game playing, constraint-satisfaction (e.g.,
configuration) and automatic induction (machine learning).  It is a
rudimentary component of AI's conceptual framework, needed for
understanding and thinking about most AI problems and solutions.

For this homework, you will implement standard search techniques and
explore heuristic measures of your own design for a palindrome
discovery system.  The system successfully derives palindromic
sequences of words, many of which are meaningful (e.g., ``Name none,
Dr. Arden: one man.''), and achieves what is to the author's knowledge
the first automatic deduction of palindromes.  Code is made available
to students which implements the state space for palindrome search
(available on-line at http://www.cs.columbia.edu/\verb$~$evs/ai/).



\section{The Charm of Palindromes}

{\it Revolted I -- Bidet, lover!}

Palindromes, which are spelled the same forward and backwards, are
likely to attract the interest of many students because of their
intrinsic appeal -- it is fascinating to see what is possible when
placing such a mundane, syntactic constraint on a list of words that
are to combine at a profoundly higher, semantic level.  To the
author's knowledge, there has been no previous work in automatic
palindrome generation.

Classic palindromes created by humans include, ``Madam, I'm Adam'',
``A man, a plan, a canal; Panama'', ``Doc note, I dissent, a fast
never prevents a fatness; I diet on cod'', ``Net safety? Byte
fasten.''  (possibly the first palindrome joke, created by the author;
coincidentally, the system subsequently found ``net-safe fasten''),
and, ``Satan oscillate my metallic sonatas.''  Such a palindrome is
the ``Holy Grail'' of automated palindrome generation, tantalizing and
motivating our students.

The infatuation and potential obsession with palindromes is reflected
by many web sites easily located with a web search engine.  For
example, freenet.buffalo.edu/\verb$~$cd431/palindromes.html lists
hundreds of premier palindromes, and
http://www.sirius.com/\verb$~$asavage/savagepalindromes.html says,
``Ever since I first heard that little bit of esoteric verse, I was
addicted.''  Other similar word games include anagram creation, which
has been implemented (see ``Anagram Genius'' at
http://mmm.mbhs.edu/\verb$~$bconnell/anagrams.html).  A recently
developed system performs at the level of a human expert on solving
crossword puzzles, another word game of constraints \cite{keim}.

Students can spend a few minutes on their own attempting to create
palindromes.  In doing this they can think about how the process they
are following could be formalized as an algorithm.



\section{AI Search for Palindromes}

{\it Elf farm raffle.}

For the purposes of this assignment, we approach the modest
problem of finding sequences of English words and proper nouns that
are palindromic, with no constraints on their grammaticality or
meaningfulness.  Therefore, resulting palindromes must be
manually filtered to determine which ones are worthy of exposition.
Incorporating additional heuristics to ensure grammaticality is a
viable project for more advanced AI projects, and for the moment will
provide the student food for thought.

To discover a palindromic string of words is a constraint satisfaction
problem (CSP).  In this case, the constraints are that each word come
from a finite dictionary, and that each letter be the same as its
symmetrically corresponding letter.

The first step towards approaching a CSP is to define the state space
for the search.  Some constraints must be alleviated in determining
the initial state from which to search -- we may start either with a
palindromic string of letters and hope to find words, or start with a
string of words and hope to form a palindrome.  The latter approach
suffers from the potential problem that every change of a word affects
a number of letters, and therefore can violate a number of palindromic
constraints.  However, words could be sought that minimize such
violations, and this becomes closer to the former approach, which
is the one we adopt.

A palindromic string of letters is defined simply by half of the
string.  Therefore, each search state is defined by a string of
letters which, when read forward and then backwards, or vice versa, is a
palindrome.  An odd-length palindrome is created by skipping the
letter where the direction is reversed.  The initial state is created
by selecting a word randomly from the dictionary, or with a word
determined by the user.

Operations that transform a state into a successor state simply {\it
realize} a word within the string of letters, either forward or
backwards, which may or may not entail adding letters to the string.
For example, consider the initial state ``safety''.  The word ``byte''
can be realized in reverse, resulting in ``safetyb''.

Each state also determines what words have been realized within the
string of letters, in both directions, and which letters are as-yet
unused, in both directions.  The current example has one word going
forward, one unused letter going forward (``b''), one word going
backwards, and three unused letters going backwards (``fas'').

Continuing with this example, these three letters start the word
``fasten'', which is therefore realized in reverse, resulting in
``netsafetyb''.  This state has two words going in reverse, but only
one going forward.  The letters ``net'' as well as ``b'' have not been
used in forward direction.  ``Net'' is a word in the dictionary, so it
is realized (this operation does not actually add any letters),
resulting in the same string of letters, but with only one unused
letter, ``b''.

Goal states are recognized if all letters are used in both directions,
or if all but one letter at either the beginning or end of the string
are used.  Therefore, the current example is recognized as a goal, and
is read forward and then backwards, skipping the ``b'' on the way
forward, adding spaces between words: ``net safety byte fasten''.

In general, possible operations are defined by realizing words that
``hang off'' the beginning or end of the string where there are unused
letters.  Symmetrically, these operations are also defined for the
string going in reverse.

These operations can result in {\it islands}, sequences of unused
letters that are ``trapped'' mid-string, surround by used letters.
Therefore, additional operations are defined which realized a word
that consumes all or part of an island, in either direction.  Such
operations never change or add more letters to the string; they just
``eat up'' unused but pre-existing letters, committing them to be
words (which already happened to fortunately be there).

There are often less (or no) options for operations that consume part
of an island, compared to options that involve adding letters.
Therefore, the successor function is constrained so that if an island
exists, successor states only include those resulting from operations
that consume part of the island.  As a result, if there is an island,
but there are no words in the dictionary to fill (part of) the island,
the successor function returns the empty set.

This built-in heuristic of the successor function serves as an
effective pedagogical example of the most-constrained-variable
heuristic for CSPs \cite{bitner,russell}.  It forces the searching
algorithm to fill islands first, so that less time is wasted on states
with islands that have no real words.  This can be thought of as a
``failure'', e.g., at a terminal of depth-first search.

A dictionary of 80,282 word forms was derived from the CELEX lexical
database \cite{CELEX} and the spell-checking dictionary on Unix
systems.  This includes many proper nouns (e.g., countries and common
names), acronyms, and all inflections and word forms (e.g., singular
and plural nouns, verb inflections and declensions).


\section{Student Assignment}

{\it Dumb, O Java; Java job mud.}

You're job is to implement depth-first, greedy, A*, and hill-climbing
search.  Also implement a special ``greedy depth-first'' in which the
queuing function adds new nodes according to their heuristic value
(that is the order in which the new nodes are added to the front is
according their heuristic value, but when new nodes are added, the
order of the nodes already in the queue does not change -- all the
successors of the expanded node are added to the front, but are
ordered first).  Additional algorithms can be optionally implemented.

Additionally, at least 3 heuristic functions
should be implemented.  These heuristics can be
similar to one another.

Several combinations of search algorithms and heuristic functions are
compared for success at finding palindromes, according to the details
given below in Section~\ref{compsearch}.

We provide for the students an implementation of the state space in
Java.  In particular, this is simply a class, PalindromeState, with a
method, Expand(), that returns a set (Vector) of PalindromeStates.
This is the set of successor states achievable by legal search
operations.  PalindromeState can be initialized with a string, or it
will select a random word for initialization.  Also available are
boolean GoalTest(), and a print() method.


\subsection{Uninformed search}

Given the implementation, it is simple for students to
immediately implement an uninformed search (a.k.a. blind search) from
scratch using a queue.

One pragmatic concern is that many states may have too large a number
of successors, on the order of the dictionary's size.  For example,
``atop'', with one word going forward, and one word, ``pot'', going
backwards, has a dangling ``a''.  Successors will include all words
starting with that letter.  Therefore, an option that is probably
necessary is to flag Expand() for only a (random) subset of
successors.  This adds a stochastic element to palindrome generation,
so multiple runs from a given initial state (inputted word) will
provide multiple palindromes with that word.

This is a modification of canonical search strategies, and provides an
opportunity to explore a second heuristic implicitly implemented by
the successor function: If a word can be realized (within an island,
touching an edge, or leaving only one unused letter on the edge)
without adding new letters to the state, the resulting state is
invariably included in the set of successors (even if the rest of the
set is selected stochastically), since it is closer to being a
complete palindrome.


\subsection{Heuristic functions}

In order to do informed search methods such as greedy search, A*
search, hill-climbing, or simulated annealing, students must implement
a heuristic function that produces a numerical rating for a state.

The development of heuristic functions for palindrome search is
elusive, thought-provoking, and challenging.  Since some are bound to
work better than others, students are exposed to experimental work
immediately, which is appropriate for a new field such as AI that is
predominated by research work.

PalindromeState also has several methods to access characteristics of
the state in order to implement this type of evaluation measure.  This
measure should be implemented by students as a method for a class
deriving from (subsumed by) PalindromeState.
The following methods are available, and reflect measures
over the entire palindromic string (not just the ``half-string''
that suffices to define a state):
\begin{itemize}
\item {\tt int length() } - number of letters
\item {\tt int nWords() } - number of realized words
\item {\tt char getLetter(int i) } - letter at location {\it i}
\item {\tt boolean used(int i) } - is letter {\it i} part of a realized word?
\end{itemize}

The range of possible heuristics is open-ended, and up
to the student's imagination.  Reasonable components include:
\begin{itemize}
\item 	sizes and numbers of islands
\item 	sizes and numbers of unused strings that touch an edge
\item 	number of unused characters
\item 	number of consonants in a row
\item 	all of the above relative to total number of letters
\end{itemize}

Additional heuristics may be designed to increase
not only the likelihood of finding a palindromic string
of words, but also to increase the subjective
quality of discovered palindromes, e.g., number of words,
average size of words, etc.


\subsection{Comparing search techniques}
\label{compsearch}

You are now in a position to conduct empirical experiments comparing
various searches and heuristics.  The goal is to minimize the number
of search nodes generated per discovery of a palindrome.  This
``failure rate'' or ``density function'' should be measured over
multiple search runs, given a choice of: heuristic, search method,
maximum number of words per palindrome, and maximum successor function
set size (the latter two may be left at their default values -- see
the code's README file).  Furthermore, this process may be modified by
placing an upper limit on the number of expanded nodes before
restarting the search, since some initial states prove to be difficult
to search from (your choice).  Additionally, when a palindrome is
found, the search does not have to end, since many other palindromes
may be found from earlier choicepoints in this same search (your
choice).

Multiple runs may need to go overnight to collect
enough data.


\subsection{Writeup and Collaboration}

Make an organized table of your results, and an accompanying paragraph
that describes the table's contents, and what choices you made.  Then
write another short paragraph drawing any intuitive conclusions you
can from the results shown in your table -- which search and heuristic
was most successful, and can you hazard a guess as to why?

You have the option to team up and collaborate with other students
for this part.  Although everyone is responsible for their
own implementation of the search algorithms, you may
team up and design complementary sets of experiments, if
you so desire.  In this case, hand in two separate submissions,
but the writeup summarizing the results can be the
same across submissions -- make it explicit who you worked
with.  It is recommended to not work with more than
one other person, and a team of 3 is the max allowed.


\subsection{Other extensions -- OPTIONAL}

Many other optional extensions to this system can be used to improve the
grammaticality or subjective desirability of resulting palindromes.
These are listed here to primarily just to provide food for thought.
These can be in the form of heuristics, search constraints, or
post-processing.  Some possibilities include:

\begin{itemize}
\item Alterations to the dictionary:
\begin{itemize}
\item 	slang words
\item 	other languages (``Amigo no gima'')
\item 	the subset of words that are dominated with common letters
\item the subset of words with simpler letter patterns, e.g., not too
many consonants in a row
\item 	a simple, small word set (``Madam, I'm Adam.'')
\end{itemize}

\item 
Heuristics designed to measure the subjective desirability of
palindromes can be evaluated by manually counting the number of
meaningful or grammatical palindromes discovered over multiple
searches.  Furthermore, the heuristic measurements can be used to
order resulting palindromes in an attempt to minimize the number that
must be searched manually for meaningfulness.

\item The following advanced extensions are most definitely
outside the scope of this assignment:
\begin{itemize}
\item Allow it to realize words such that they wrap around
the edge of the ``half-string''.  Certain words
that are partially palindromic can do this, e.g., ``Adam''
in ``Palm, Adam; lap'', and ``Toyota'' in ``A Toyota''.
\item Incorporating selectional constraints on words based on
part-of-speech to improve grammaticality.
\item Filter the system's output with a natural language parser
to find grammatical palindromes.
\item Methods to find palindromes that follow collocational
constraints on words, e.g., ``take-bath,'' ``make-deposit,''
or ``look up''.
\item Methods to put semantically related words together
in the same palindrome, e.g., with the Wordnet, a 
lexicon that encodes the semantic relationships between
words \cite{miller}.
\end{itemize}
\end{itemize}



\section{Results}

Students are asked to email the instructor (evs@cs.columbia.edu) with
particularly good palindromes to be added to an on-line collection.

The following example results are from uninformed, depth-first search
with a maximum of 6 words per palindrome.  About 1\% of produced
palindromes were deemed meaningful by the author.  The current
implementation produces several thousand palindromes a
day.\footnote{The author is glad to email you a slew if you'd like to
hash through some!}  Punctuation and capitalization for all
palindromes in this section were determined by the author.

The following were produced from searches seeded with one of the
words: {\it AI, OOP, Java, taught, SIG,} or {\it computer}:
\begin{itemize}
\item On AI, play Al piano.
\item Poor OOP.
\item SUN, a Java Janus.  (God)
\item Dumb, O Java; Java job mud.
\item ALA me taught: Evil liveth Guatemala.
\item Debra, Java, LSD, Slav; ajar bed.
\item Plato grasp OOP -- poops argot alp.
\item Poofs note rap -- pareto NSF-OOP.
\item Poops?  I lewd!  We LISP OOP.
\item Poor iambics USC IBM air OOP.
\item Ahem, ANSI SIG: Isis name -- ha!
\item Ah computer, fret up; mocha.
\item ``Adieu; grasp OOP - oops!'' argue Ida.
\item None: Decimal SIG, Islamic Eden, on!
\end{itemize}

The following were deemed grammatical by the author, and
were produced from searches seeded with random
words:
\begin{itemize}

\item Infinitesimal clam I set in Ifni.
\item Twenties acne?  Encase it, Newt.
\item Name none, Dr. Arden: one man.
\item Revolted I -- Bidet, lover!
\item Deepmined gossip piss, Ogden -- I'm peed.
\item Wow! Wop powwow.
\item Elf farm raffle.
\item Net-safe fasten.
\item Madame Nile pips pipeline, madam.
\item Tangy gnat.
\item Evade Dave.
\item Re-sampled art?  Trade LP maser.
\item A mini-mower crew-o-minima.
\item Nomad do-gooder, redo.  O, goddam -- on!
\item Redo? O Goddam -- on, nomad do-gooder!
\item Wo, honey's deeds -- ye nohow!
\item Hex, a jam!  Ajax, eh?
\item A ha-ha-foolery: Gyre loofah, aha!
\item ETA misdeeds? I mate.

\end{itemize}

The following were not deemed grammatical, but win
honorable mention:
\begin{itemize}
\item Gentlewoman I dine mo' -- welt neg.
\item Spacecapsule dome remodel U.S. pace caps.
\item Sex elicit ore erotic ilexes
\item A retaliatory pyro tail at ERA.
\item Nil murderer, evil liver, ere drumlin.
\item Nob Beebe, oh Phoebe, ebb on.
\end{itemize}


\section{Related Work}

Informally, formulating a sentence
is a search (``searching for the right words''), and, in fact, work in
automatic natural language generation formulates sentence generation
as a search to fulfill multiple constraints, such as maximal
grammatical nesting, selectional constraints between words
\cite{smadja}, and the logical ordering of ideas \cite{mckeown}.


\section{Alternative to Palindromes}

For students who do not wish to program in Java,
your assignment is to implement the same
search strategies and do the same comparisons
of heuristics and search as described above, except choose one
of the following search problems:

\begin{itemize}
\item 8-puzzle
\item U2 problem with varying band sizes (4 members, 5, etc.)
\item That solitary game in which pegs jump
over other pegs and then you get to remove a peg
and the goal is to leave only one peg.
\item Palindromes -- implement it from scratch, using my dictionary
if you like.  If you choose to do this you can formalize
the search space in a different way if you have another idea
as to how to do this.  But in any case, be warned, it will
be a fair amount of overhead.
\item Anagrams.
\item Another alternative of your choosing (but
email the instructor for permission first).
\end{itemize}


%\section*{acknowledgments}

%{\it Name none, Dr. Arden: one man.}

%I'd like to thank all the little people.


\bibliographystyle{sigcse}
\bibliography{/u/boat/evs/prop/prop}
\end{document}
