Navigation Planning to Guide Concept Understanding
in the World Wide Web
Seiji Yamada

Yukio Ohsawa

CISS, IGSSE
Tokyo Institute of Technology
4259 Nagatsuta, MidoriYokohama 226-8502, Japan

Department of Systems and Human ScienceTsukuba University
3-29-1 Ohtsuka, Bunkyou
Tokyo 112-0012, Japan

yamada@ymd.dis.titech.ac.jp

osawa@gssm.otsuka.tsukuba.ac.jp

ABSTRACTThis paper describes navigation planning that generates aplan for guiding concept understanding in the WWW. It also
has the ability to generate operators during planning fromWeb pages. For understanding a concept, it is a useful way
to browse for relevant Web pages in the WWW. However
this task is very hard because the user has to search for themin the vast WWW. To deal with this problem, we propose
navigation planning to generate a sequence of Web pages bywhich a user systematically understand a concept.

1. INTRODUCTION
The WWW is very useful for a user who wants to understanda target concept . He/she can browse helpful Web pages tounderstand a target concept. However, in general, this taskis very hard because he/she may not know where such Web
pages are, and has to search them over the vast WWW
search space. A solution of the problem is to use a searchengine with the target concept as a query. However, since
the retrieved Web pages are not ﬁltered suﬃciently, a user
has to select useful ones from them. Furthermore, since inmost cases the retrieved Web pages include concepts thata user does not understand, he/she must search the useful
Web pages for them using a search engine again. This task
is repeated until a user understands the target concept, andwastes time. We consider the task as planning, and propose
navigation planning [4] to automatically generate a sequenceof Web pages which can guide a user to understand a target
concept.

2. NAVIGATION PLANNING
In this research, navigation means a task that indicates useful Web pages to a user for guiding his/her concept understanding. A sequence of useful Web pages is called a plan ,and navigation planning means the automatic generation ofthe plan. We can summarize the task in the following. This
procedure is iterated until terminated by the user.

1. Search Web pages using a search engine.
2. Understand the pages retrieved by the search engine.
3. Select unknown concepts in the Web pages.
4. Go to Step1 with unknown concepts as target concepts.
The procedure above is considered planning [1] using the following correspondence. Using this formalization, we can apply a classical planning framework to navigation planning.
• Action : Understanding concepts in a Web page.
• State : A user’s knowledge state described with a setof words describing concepts which he/she knows.
• Initial state : A user’s initial knowledge state.
• Goal state : A target concept described with a set ofwords which a user wants to understand.
• Operator : U-Op(URL) deﬁned by the followings.
– Label : URL of the Web page
– Condition : C = {c1 , · · · , ci }, where C means
the condition words which are necessary to understand the pages.
– Eﬀect : E = {e1 , · · · , ej }, where E is eﬀect words
which a user obtains by understanding the page.
This navigation planning contains a signiﬁcant problem which
has not been in planning thus far. It is that the U-Op(URL)
operators are not given in advance. This is because it is impossible for a human designer to generate the operators fromall the Web pages in the WWW. Hence the operators need
to be automatically generated from Web pages when they
are necessary.

3. GENERATING OPERATORS
3.1 Using TAG structure in a html file
Various methods to extract keywords from text have beenstudied[3]. Though most methods are based on the frequency of words, one of the most eﬀective methods is toutilize the structure in text. Since a Web page is describedin a HTML format , we can utilize TAG structures.
The prime candidates for condition words are the words
linked to other Web pages, i.e. the words between <A HREF=URL>
and </A>, because this tag is a sign of reference to relevant
topics, which are important for understanding the current
Web page in many cases.

Goal state

Node-1.... Node-.... Node-

Node-

Width of beam search(a) Navigation planning as
backward beam search

Subgoal of node-iqueryA search engine
Related Web pages

Page-1....

Page- w

Generating operatorswith Ext-OP
Ope-1

....

Ope- w

Generating b nodes in the next depthwith an evaluation function(b) Node expanding from node-i

Figure 1: Navigation planning.

Since the title of the Web page describes words which auser may acquire by reading the page, the words between<TITLE> and </TITLE> are candidates for the eﬀect words.
In the same way, headings describe knowledge which a user
may obtain by reading the section. Thus the words between<Hn> and </Hn> are also candidates for eﬀect words.

The extraction of condition and eﬀect words using tag structure and KeyGraph are integrated.

4. PLANNING PROCEDURE
We now develop navigation planning procedure. Fig.1 shows
the overview of our autonomous navigation planning agent,called NaviPlan . NaviPlan autonomously generates a planfor given target concepts. It uses backward beam search froma goal state (Fig.1(a)). The node expansion (Fig.1(b)) includes the search for related Web pages with a search engine
and the generation of operators.
We fully implemented NaviPlan and made various experiments with subjects for evaluation. Unfortunately, due tospace constrains, we omit them. Fig.2 shows a plan (depth= 4) generated by NaviPlan with the target concept “concept formation”.

5. CONCLUSION
We proposed a novel navigation planning method that generates a plan guiding user to understand a concept in theWWW. It also has the ability to generate operators during
planning from Web pages using keyword extraction methods. The search for useful Web pages for a user to understand goal concepts was formalized using a planning framework, and an operator corresponding to the understandingof a Web page was deﬁned with condition and eﬀect knowledge. Then we described the whole planning procedure.

6. REFERENCES[1] R. E. Fikes and N. J. Nilsson. STRIPS: A new
approach to the application of theorem proving toproblem solving. Artiﬁcial Intelligence, 2:189–208, 1971.
[2] Y. Ohsawa, N. E. Benson, and M. Yachida. KeyGraph :Automatic indexing by co-occurrence graph based onbuilding construction metaphor. In IEEE Advanced
Digital Library Conference, 12–18, 1998.
[3] G. Salton and C. Buckley. Term-weighting approaches
in automatic text retrieval. Readings in Information
Retrieval), 323–328. Morgan Kaufmann, 1997.
[4] S. Yamada and Y. Osawa. Planning to guide concept
understanding in the WWW. In AAAI 1998 Workshop
on AI and Information Integration, 121–126, 1998.

3.2 KeyGraph: A keyword extraction method
The extraction of condition and eﬀect words using only thetag structure is not suﬃcient. All the linked words are notcandidates for condition words, and all the condition words
are not linked. Thus we need to utilize another method toassist it, and KeyGraph is used.
KeyGraph is a fast method for extracting keywords representing the asserted core idea in a document[2]. KeyGraphcomposes clusters of terms, based on co-occurrences between
terms in a document. Each cluster represents a concept on
which the document is based (i.e. condition words), andterms connecting clusters tightly are obtained as author’sassertion (i.e. eﬀect words). Furthermore the likelihood for
condition and eﬀect words can be computed by KeyGraph ,and used for weight of an operator. Another merit of KeyGraph is that it does not employ a corpus.

Figure 2: Plan for “Concept formation”.