Advanced.pm untested

filter: Statementstmt 0.0% 0 / 319 Branchbran 0.0% 0 / 116 Conditioncond 0.0% 0 / 9 MC/DCmcdc 0.0% 0 / 6 Subroutinesub 0.0% 0 / 30 Podpod 0.0% 0 / 19 totaltotal 0.0% 0 / 499 CC 59 SCAR 44.9
CC
59
Cov
0%
backward
240.0
mixed
156.0
forward
110.0
CRAP 88.9
1 #
2 # AI::ExpertSystem::Advanced
3 #
4 # Author(s): Pablo Fischer (pfischer@cpan.org)
5 # Created: 11/29/2009 18:28:30 CST 18:28:30
6 package AI::ExpertSystem::Advanced;
7  
8 =head1 NAME
9  
10 AI::ExpertSystem::Advanced - Expert System with backward, forward and mixed algorithms
11  
12 =head1 DESCRIPTION
13  
14 Inspired in L<AI::ExpertSystem::Simple> but with additional features:
15  
16 =over 4
17  
18 =item *
19  
20 Uses backward, forward and mixed algorithms.
21  
22 =item *
23  
24 Offers different views, so user can interact with the expert system via a
25 terminal or with a friendly user interface.
26  
27 =item *
28  
29 The knowledge database can be stored in any format such as YAML, XML or
30 databases. You just need to choose what driver to use and you are done.
31  
32 =item *
33  
34 Uses certainty factors.
35  
36 =back
37  
38 =head1 SYNOPSIS
39  
40 An example of the mixed algorithm:
41  
42 use AI::ExpertSystem::Advanced;
43 use AI::ExpertSystem::Advanced::KnowledgeDB::Factory;
44  
45 my $yaml_kdb = AI::ExpertSystem::Advanced::KnowledgeDB::Factory->new('yaml',
46 {
47 filename => 'examples/knowledge_db_one.yaml'
48 });
49  
50 my $ai = AI::ExpertSystem::Advanced->new(
51 viewer_class => 'terminal',
52 knowledge_db => $yaml_kdb,
53 initial_facts => ['I'],
54 verbose => 1);
55 $ai->mixed();
56 $ai->summary();
57  
58 =cut
59 use Moose;
60 use AI::ExpertSystem::Advanced::KnowledgeDB::Base;
61 use AI::ExpertSystem::Advanced::Viewer::Base;
62 use AI::ExpertSystem::Advanced::Viewer::Factory;
63 use AI::ExpertSystem::Advanced::Dictionary;
64 use Time::HiRes qw(gettimeofday);
65 use YAML::Syck qw(Dump);
66  
67 our $VERSION = '0.03';
68  
69 =head1 Attributes
70  
71 =over 4
72  
73 =item B<initial_facts>
74  
75 A list/set of initial facts the algorithms start using.
76  
77 During the forward algorithm the task is to find a list of goals caused
78 by these initial facts (the only data we have in that moment).
79  
80 Lets imagine your knowledge database is about symptoms and diseases. You need
81 to find what diseases are caused by the symptoms of a patient, these first
82 symptons are the initial facts.
83  
84 Initial facts as also asked and inference facts can be negative or positive. By
85 default the initial facts are positive.
86  
87 Keep in mind that the data contained in this array can be the IDs or the name
88 of the fact.
89  
90 This array will be converted to L<initial_facts_dict>. And all the data (ids or
91 or names) will be made of only IDs.
92  
93 my $ai = AI::ExpertSystem::Advanced->new(
94 viewer_class => 'terminal',
95 knowledge_db => $yaml_kdb,
96 initial_facts => ['I', ['F', '-'], ['G', '+']);
97  
98 As you can see if you want to provide the sign of a fact, just I<encapsulate>
99 it in an array, the first item should be the fact and the second one the
100 sign.
101  
102 =cut
103 has 'initial_facts' => (
104 is => 'rw',
105 isa => 'ArrayRef[Str]',
106 default => sub { return []; });
107  
108 =item B<initial_facts_dict>
109  
110 This dictionary (see L<AI::ExpertSystem::Advanced::Dictionary> has the sasme
111 data of L<initial_facts> but with the additional feature(s) of proviing
112 iterators and a quick way to find elements.
113  
114 =cut
115 has 'initial_facts_dict' => (
116 is => 'ro',
117 isa => 'AI::ExpertSystem::Advanced::Dictionary');
118  
119 =item B<goals_to_check>
120  
121 my $ai = AI::ExpertSystem::Advanced->new(
122 viewer_class => 'terminal',
123 knowledge_db => $yaml_kdb,
124 goals_to_check => ['J']);
125  
126 When doing the L<backward()> algorithm it's required to have at least one goal
127 (aka hypothesis).
128  
129 This could be pretty similar to L<initial_facts>, with the difference that the
130 initial facts are used more with the causes of the rules and this one with
131 the goals (usually one in a well defined knowledge database).
132  
133 The same rule of L<initial_facts> apply here, you can provide the sign of the
134 facts and you can provide the id or the name of them.
135  
136 From our example of symptoms and diseases lets imagine we have the hypothesis
137 that a patient has flu, we don't know the symptoms it has, we want the
138 expert system to keep asking us for them to make sure that our hypothesis
139 is correct (or incorrect in case there's not enough information).
140  
141 =cut
142 has 'goals_to_check' => (
143 is => 'rw',
144 isa => 'ArrayRef[Str]',
145 default => sub { return []; });
146  
147 =item B<goals_to_check_dict>
148  
149 Very similar to L<goals_to_check> (and indeed of L<initial_facts_dict>). We
150 want to make the job easier.
151  
152 It will be a dictionary made of the data of L<goals_to_check>.
153  
154 =cut
155 has 'goals_to_check_dict' => (
156 is => 'ro',
157 isa => 'AI::ExpertSystem::Advanced::Dictionary');
158  
159 =item B<inference_facts>
160  
161 Inference facts are basically the core of an expert system. These are facts
162 that are found and copied when a set of facts (initial, inference or asked)
163 match with the causes of a goal.
164  
165 L<inference_facts> is a L<AI::ExpertSystem::Advanced::Dictionary>, it will
166 store the name of the fact, the rule that caused these facts to be copied to
167 this dictionary, the sign and the algorithm that triggered it.
168  
169 =cut
170 has 'inference_facts' => (
171 is => 'ro',
172 isa => 'AI::ExpertSystem::Advanced::Dictionary');
173
174 =item B<knowledge_db>
175  
176 The object reference of the knowledge database L<AI::ExpertSystem::Advanced> is
177 using.
178  
179 =cut
180 has 'knowledge_db' => (
181 is => 'rw',
182 isa => 'AI::ExpertSystem::Advanced::KnowledgeDB::Base',
183 required => 1);
184  
185 =item B<asked_facts>
186  
187 During the L<backward()> algorithm there will be cases when there's no clarity
188 if a fact exists. In these cases the L<backward()> will be asking the user
189 (via automation or real questions) if a fact exists.
190  
191 Going back to the L<initial_facts> example of symptoms and diseases. Imagine
192 the algorithm is checking a rule, some of the facts of the rule make a match
193 with the ones of L<initial_facts> or L<inference_facts> but some wont, for
194 these I<unsure> facts the L<backward()> will ask the user if a symptom (a fact)
195 exists. All these asked facts will be stored here.
196  
197 =cut
198 has 'asked_facts' => (
199 is => 'ro',
200 isa => 'AI::ExpertSystem::Advanced::Dictionary');
201  
202 =item B<visited_rules>
203  
204 Keeps a record of all the rules the algorithms have visited and also the number
205 of causes each rule has.
206  
207 =cut
208 has 'visited_rules' => (
209 is => 'ro',
210 isa => 'AI::ExpertSystem::Advanced::Dictionary');
211  
212 =item B<verbose>
213  
214 my $ai = AI::ExpertSystem::Advanced->new(
215 viewer_class => 'terminal',
216 knowledge_db => $yaml_kdb,
217 initial_facts => ['I'],
218 verbose => 1);
219  
220 By default this is turned off. If you want to know what happens behind the
221 scenes turn this on.
222  
223 Everything that needs to be debugged will be passed to the L<debug()> method
224 of your L<viewer>.
225  
226 =cut
227 has 'verbose' => (
228 is => 'rw',
229 isa => 'Bool',
230 default => 0);
231  
232 =item B<viewer>
233  
234 Is the object L<AI::ExpertSystem::Advanced> will be using for printing what is
235 happening and for interacting with the user (such as asking the
236 L<asked_facts>).
237  
238 This is practical if you want to use a viewer object that is not provided by
239 L<AI::ExpertSystem::Advanced::Viewer::Factory>.
240  
241 =cut
242 has 'viewer' => (
243 is => 'rw',
244 isa => 'AI::ExpertSystem::Advanced::Viewer::Base');
245  
246 =item B<viewer_class>
247  
248 Is the the class name of the L<viewer>.
249  
250 You can decide to use the viewers L<AI::ExpertSystem::Advanced::Viewer::Factory>
251 offers, in this case you can pass the object or only the name of your favorite
252 viewer.
253  
254 =cut
255 has 'viewer_class' => (
256 is => 'rw',
257 isa => 'Str',
258 default => 'terminal');
259  
260 =item B<found_factor>
261  
262 In your knowledge database you can give different I<weights> to the facts of
263 each rule (eg to define what facts have more I<priority>). During the
264 L<mixed()> algorithm it will be checking what causes are found in the
265 L<inference_facts> and in the L<asked_facts> dictionaries, then the total
266 number of matches (or total number of certainity factors of each rule) will
267 be compared versus the value of this factor, if it's higher or equal then the
268 rule will be triggered.
269  
270 You can read the documentation of the L<mixed()> algorithm to know the two
271 ways this factor can be used.
272  
273 =cut
274 has 'found_factor' => (
275 is => 'rw',
276 isa => 'Num',
277 default => '0.5');
278  
279 =item B<shot_rules>
280  
281 All the rules that are shot are stored here. This is a hash, the key of each
282 item is the rule id while its value is the precision time when the rule was
283 shot.
284  
285 The precision time is useful for knowing when a rule was shot and based on that
286 you can know what steps it followed so you can compare (or reproduce) them.
287  
288 =back
289  
290 =cut
291 has 'shot_rules' => (
292 is => 'ro',
293 isa => 'HashRef[Str]');
294  
295 =head1 Constants
296  
297 =over 4
298  
299 =item * B<FACT_SIGN_NEGATIVE>
300  
301 Used when a fact is negative, aka, a fact doesn't happen.
302  
303 =cut
304 use constant FACT_SIGN_NEGATIVE => '-';
305  
306 =item * B<FACT_SIGN_POSITIVE>
307  
308 Used for those facts that happen.
309  
310 =cut
311 use constant FACT_SIGN_POSITIVE => '+';
312  
313 =item * B<FACT_SIGN_UNSURE>
314  
315 Used when there's no straight answer of a fact, eg, we don't know if an answer
316 will change the result.
317  
318 =back
319  
320 =cut
321 use constant FACT_SIGN_UNSURE => '~';
322  
323 =head1 Methods
324  
325 =head2 B<shoot($rule, $algorithm)>
326  
327 Shoots the given rule. It will do the following verifications:
328  
329 =over 4
330  
331 =item *
332  
333 Each of the facts (causes) will be compared against the L<initial_facts_dict>,
334 L<inference_facts> and L<asked_facts> (in this order).
335  
336 =item *
337  
338 If any initial, inference or asked fact matches with a cause but it's negative
339 then all of its goals (usually only one by rule) will be copied to the
340 L<inference_facts> with a negative sign, otherwise a positive sign will be
341 used.
342  
343 =item *
344  
345 Will add the rule to the L<shot_rules> hash.
346  
347 =back
348  
349 =cut
350 sub shoot {
351 my ($self, $rule, $algorithm) = @_;
352  
353 $self->{'shot_rules'}->{$rule} = gettimeofday;
354  
355 my $rule_causes = $self->get_causes_by_rule($rule);
356 my $rule_goals = $self->get_goals_by_rule($rule);
357 my $any_negation = 0;
358 $rule_causes->populate_iterable_array();
359 while(my $caused_fact = $rule_causes->iterate) {
360 # Now, from the current rule fact, any of the facts were marked
361 # as *negative* from the initial facts, inference or asked facts?
362 $any_negation = 0;
363 foreach my $dict (qw(initial_facts_dict inference_facts asked_facts)) {
364 # Also make sure we are going to read from position 0 in our dicts
365 $self->{$dict}->populate_iterable_array();
366 while(my $dict_fact = $self->{$dict}->iterate) {
367 if ($dict_fact eq $caused_fact) {
368 if ($self->is_fact_negative(
369 $dict,
370 $dict_fact)) {
371 $any_negation = 1;
372 last;
373 }
374 }
375 }
376 }
377 # anything negative?
378 if ($any_negation) {
379 last;
380 }
381 }
382 my $sign = ($any_negation) ? FACT_SIGN_NEGATIVE : FACT_SIGN_POSITIVE;
383 # Copy the goal(s) of this rule to our "initial facts"
384 $self->copy_to_inference_facts($rule_goals, $sign, $algorithm, $rule);
385 }
386  
387 =head2 B<is_rule_shot($rule)>
388  
389 Verifies if the given C<$rule> has been shot.
390  
391 =cut
392 sub is_rule_shot {
393 my ($self, $rule) = @_;
394  
395 return defined $self->{'shot_rules'}->{$rule};
396 }
397  
398 =head2 B<get_goals_by_rule($rule)>
399  
400 Will ask the L<knowledge_db> for the goals of the given C<$rule>.
401  
402 A L<AI::ExpertSystem::Advanced::Dictionary> will be returned.
403  
404 =cut
405 sub get_goals_by_rule {
406 my ($self, $rule) = @_;
407 return $self->{'knowledge_db'}->rule_goals($rule);
408 }
409  
410 =head2 B<get_causes_by_rule($rule)>
411  
412 Will ask the L<knowledge_db> for the causes of the given C<$rule>.
413  
414 A L<AI::ExpertSystem::Advanced::Dictionary> will be returned.
415  
416 =cut
417 sub get_causes_by_rule {
418 my ($self, $rule) = @_;
419 return $self->{'knowledge_db'}->rule_causes($rule);
420 }
421  
422 =head2 B<is_fact_negative($dict_name, $fact)>
423  
424 Will check if the given C<$fact> of the given dictionary (C<$dict_name>) is
425 negative.
426  
427 =cut
428 sub is_fact_negative {
429 my ($self, $dict_name, $fact) = @_;
430  
431 my $sign = $self->{$dict_name}->get_value($fact, 'sign');
432 if (!defined $sign) {
433 confess "This fact ($fact) does not exists!";
434 }
435 return $sign eq FACT_SIGN_NEGATIVE;
436 }
437  
438 =head2 B<copy_to_inference_facts($facts, $sign, $algorithm, $rule)>
439  
440 Copies the given C<$facts> (a dictionary, usually goal(s) of a rule) to the
441 L<inference_facts> dictionary. All the given goals will be copied with the
442 given C<$sign>.
443  
444 Additionally it will add the given C<$algorithm> and C<$rule> to the inference
445 facts. So later we can know how we got to a certain inference fact.
446  
447 =cut
448 sub copy_to_inference_facts {
449 my ($self, $facts, $sign, $algorithm, $rule) = @_;
450  
451 while(my $fact = $facts->iterate) {
452 $self->{'inference_facts'}->append(
453 $fact,
454 {
455 name => $fact,
456 sign => $sign,
457 factor => 0.0,
458 algorithm => $algorithm,
459 rule => $rule
460 });
461 }
462 }
463  
464 =head2 B<compare_causes_with_facts($rule)>
465  
466 Compares the causes of the given C<$rule> with:
467  
468 =over 4
469  
470 =item *
471  
472 Initial facts
473  
474 =item *
475  
476 Inference facts
477  
478 =item *
479  
480 Asked facts
481  
482 =back
483  
484 It will be couting the matches of all of the above dictionaries, so for example
485 if we have four causes, two make match with initial facts, other with inference
486 and the remaining one with the asked facts, then it will evaluate to true since
487 we have a match of the four causes.
488  
489 =cut
490 sub compare_causes_with_facts {
491 my ($self, $rule) = @_;
492
493 my $causes = $self->get_causes_by_rule($rule);
494 my $match_counter = 0;
495 my $causes_total = $causes->size();
496
497 while (my $cause = $causes->iterate) {
498 foreach my $dict (qw(initial_facts_dict inference_facts asked_facts)) {
499 if ($self->{$dict}->find($cause)) {
500 $match_counter++;
501 }
502 }
503 }
504 return $match_counter eq $causes_total;
505 }
506  
507 =head2 B<get_causes_match_factor($rule)>
508  
509 Similar to L<compare_causes_with_facts()> but with the difference that it will
510 count the L<match factor> of each matched cause and return the total of this
511 weight.
512  
513 The match factor is used by the L<mixed()> algorithm and is useful to know if
514 a certain rule should be shoot or not even if not all of the causes exist
515 in our facts.
516  
517 The I<match factor> is calculated in two ways:
518  
519 =over 4
520  
521 =item *
522  
523 Will do a sum of the weight for each matched cause. Please note that if only
524 one cause of a rule has a specified weight then the remaining causes will
525 default to the total weight minus 1 and then divided with the total number
526 of causes (matched or not) that don't have a weight.
527  
528 =item *
529  
530 If no weight is found with all the causes of the given rule, then the total
531 number of matches will be divided by the total number of causes.
532  
533 =back
534  
535 =cut
536 sub get_causes_match_factor {
537 my ($self, $rule) = @_;
538  
539 my $causes = $self->get_causes_by_rule($rule);
540 my $causes_total = $causes->size();
541  
542 my ($factor_counter, $missing_factor, $match_counter, $nonfactor_match) =
543 (0, 0, 0, 0);
544
545 while (my $cause = $causes->iterate) {
546 my $factor = $causes->get_value($cause, 'factor');
547 if (!defined $factor) {
548 $missing_factor++;
549 }
550 foreach my $dict (qw(initial_facts_dict inference_facts asked_facts)) {
551 if ($self->{$dict}->find($cause)) {
552 $match_counter++;
553 if (defined $factor) {
554 $factor_counter = $factor_counter + $factor;
555 } else {
556 $nonfactor_match++;
557 }
558 }
559 }
560 }
561 # No matches?
562 if ($match_counter eq 0) {
563 return 0;
564 }
565 # None of the causes (matched or not) have a factor
566 if ($causes_total eq $missing_factor) {
567 return $match_counter / $causes_total;
568 } else { # Some factors found
569 if ($missing_factor) { # Oh, but some causes don't have it
570 return $factor_counter + ($nonfactor_match / $causes_total);
571 } else {
572 return $factor_counter;
573 }
574 }
575 }
576  
577 =head2 B<is_goal_in_our_facts($goal)>
578  
579 Checks if the given C<$goal> is in:
580  
581 =over 4
582  
583 =item 1
584  
585 The initial facts
586  
587 =item 2
588  
589 The inference facts
590  
591 =item 3
592  
593 The asked facts
594  
595 =back
596  
597 =cut
598 sub is_goal_in_our_facts {
599 my ($self, $goal) = @_;
600  
601 foreach my $dict (qw(initial_facts_dict inference_facts asked_facts)) {
602 if ($self->{$dict}->find($goal)) {
603 return 1;
604 }
605 }
606 return undef;
607 }
608  
609 =head2 B<remove_last_ivisited_rule()>
610  
611 Removes the last visited rule and return its number.
612  
613 =cut
614 sub remove_last_visited_rule {
615 my ($self) = @_;
616  
617 my $last = $self->{'visited_rules'}->iterate;
618 if (defined $last) {
619 $self->{'visited_rules'}->remove($last);
620 $self->{'visited_rules'}->populate_iterable_array();
621 }
622 return $last;
623 }
624  
625 =head2 B<visit_rule($rule, $total_causes)>
626  
627 Adds the given C<$rule> to the end of the L<visited_rules>.
628  
629 =cut
630 sub visit_rule {
631 my ($self, $rule, $total_causes) = @_;
632  
633 $self->{'visited_rules'}->prepend($rule,
634 {
635 causes_total => $total_causes,
636 causes_pending => $total_causes
637 });
638 $self->{'visited_rules'}->populate_iterable_array();
639 }
640  
641 =head2 B<copy_to_goals_to_check($rule, $facts)>
642  
643 Copies a list of facts (usually a list of causes of a rule) to
644 L<goals_to_check_dict>.
645  
646 The rule ID of the goals that are being copied is also stored in the hahs.
647  
648 =cut
649 sub copy_to_goals_to_check {
650 my ($self, $rule, $facts) = @_;
651  
652 while(my $fact = $facts->iterate_reverse) {
653 $self->{'goals_to_check_dict'}->prepend(
654 $fact,
655 {
656 name => $fact,
657 sign => $facts->get_value($fact, 'sign'),
658 rule => $rule
659 });
660 }
661 }
662  
663 =head2 B<ask_about($fact)>
664  
665 Uses L<viewer> to ask the user for the existence of the given C<$fact>.
666  
667 The valid answers are:
668  
669 =over 4
670  
671 =item B<+> or L<FACT_SIGN_POSITIVE>
672  
673 In case user knows of it.
674  
675 =item B<-> or L<FACT_SIGN_NEGATIVE>
676  
677 In case user doesn't knows of it.
678  
679 =item B<~> or L<FACT_SIGN_UNSURE>
680  
681 In case user doesn't have any clue about the given fact.
682  
683 =back
684  
685 =cut
686 sub ask_about {
687 my ($self, $fact) = @_;
688  
689 # The knowledge db has questions for this fact?
690 my $question = $self->{'knowledge_db'}->get_question($fact);
691 if (!defined $question) {
692 $question = "Do you have $fact?";
693 }
694 my @options = qw(Y N U);
695 my $answer = $self->{'viewer'}->ask($question, @options);
696 return $answer;
697 }
698  
699 =head2 B<get_rule_by_goal($goal)>
700  
701 Looks in the L<knowledge_db> for the rule that has the given goal. If a rule
702 is found its number is returned, otherwise undef.
703  
704 =cut
705 sub get_rule_by_goal {
706 my ($self, $goal) = @_;
707  
708 return $self->{'knowledge_db'}->find_rule_by_goal($goal);
709 }
710  
711 =head2 B<forward()>
712  
713 use AI::ExpertSystem::Advanced;
714 use AI::ExpertSystem::Advanced::KnowledgeDB::Factory;
715  
716 my $yaml_kdb = AI::ExpertSystem::Advanced::KnowledgeDB::Factory->new('yaml',
717 {
718 filename => 'examples/knowledge_db_one.yaml'
719 });
720  
721 my $ai = AI::ExpertSystem::Advanced->new(
722 viewer_class => 'terminal',
723 knowledge_db => $yaml_kdb,
724 initial_facts => ['F', 'J']);
725 $ai->forward();
726 $ai->summary();
727  
728 The forward chaining algorithm is one of the main methods used in Expert
729 Systems. It starts with a set of variables (known as initial facts) and reads
730 the available rules.
731  
732 It will be reading rule by rule and for each one it will compare its causes
733 with the initial, inference and asked facts. If all of these causes are in the
734 facts then the rule will be shoot and all of its goals will be copied/converted
735 to inference facts and will restart reading from the first rule.
736  
737 =cut
738 sub forward {
739 my ($self) = @_;
740  
741 confess "Can't do forward algorithm with no initial facts" unless
742 $self->{'initial_facts_dict'};
743  
744 my ($more_rules, $current_rule) = (1, undef);
745 while($more_rules) {
746 $current_rule = $self->{'knowledge_db'}->get_next_rule($current_rule);
747  
748 # No more rules?
749 if (!defined $current_rule) {
750 $self->{'viewer'}->debug("We are done with all the rules, bye")
751 if $self->{'verbose'};
752 $more_rules = 0;
753 last;
754 }
755  
756 $self->{'viewer'}->debug("Checking rule: $current_rule") if
757 $self->{'verbose'};
758
759 if ($self->is_rule_shot($current_rule)) {
760 $self->{'viewer'}->debug("We already shot rule: $current_rule")
761 if $self->{'verbose'};
762 next;
763 }
764  
765 $self->{'viewer'}->debug("Reading rule $current_rule")
766 if $self->{'verbose'};
767 $self->{'viewer'}->debug("More rules to check, checking...")
768 if $self->{'verbose'};
769  
770 my $rule_causes = $self->get_causes_by_rule($current_rule);
771 # any of our rule facts match with our facts to check?
772 if ($self->compare_causes_with_facts($current_rule)) {
773 # shoot and start again
774 $self->shoot($current_rule, 'forward');
775 # Undef to start reading from the first rule.
776 $current_rule = undef;
777 next;
778 }
779 }
780 return 1;
781 }
782  
783 =head2 B<backward()>
784  
785 use AI::ExpertSystem::Advanced;
786 use AI::ExpertSystem::Advanced::KnowledgeDB::Factory;
787  
788 my $yaml_kdb = AI::ExpertSystem::Advanced::KnowledgeDB::Factory->new('yaml',
789 {
790 filename => 'examples/knowledge_db_one.yaml'
791 });
792  
793 my $ai = AI::ExpertSystem::Advanced->new(
794 viewer_class => 'terminal',
795 knowledge_db => $yaml_kdb,
796 goals_to_check => ['J']);
797 $ai->backward();
798 $ai->summary();
799  
800 The backward algorithm starts with a set of I<assumed> goals (facts). It will
801 start reading goal by goal. For each goal it will check if it exists in the
802 initial, inference and asked facts (see L<is_goal_in_our_facts()>) for more
803 information).
804  
805 =over 4
806  
807 =item *
808  
809 If the goal exist then it will be removed from the dictionary, it will also
810 verify if there are more visited rules to shoot.
811  
812 If there are still more visited rules to shoot then it will check from what
813 rule the goal comes from, if it was copied from a rule then this data will
814 exist. With this information then it will see how many of the causes of this
815 given rule are still in the L<goals_to_check_dict>.
816  
817 In case there are still causes of this rule in L<goals_to_check_dict> then the
818 amount of causes pending will be reduced by one. Otherwise (if the amount is
819 0) then the rule of this last removed goal will be shoot.
820  
821 =item *
822  
823 If the goal doesn't exist in the mentioned facts then the goal will be searched
824 in the goals of every rule.
825  
826 In case it finds the rule that has the goal, this rule will be marked (added)
827 to the list of visited rules (L<visited_rules>) and also all of its causes
828 will be added to the top of the L<goals_to_check_dict> and it will start
829 reading again all the goals.
830  
831 If there's the case where the goal doesn't exist as a goal in the rules then
832 it will ask the user (via L<ask_about()>) for the existence of it. If user is
833 not sure about it then the algorithm ends.
834  
835 =back
836  
837 =cut
838 sub backward {
839 my ($self) = @_;
840  
841 my ($more_goals, $current_goal, $total_goals) = (
842 1,
843 0,
844 scalar(@{$self->{'goals_to_check'}}));
845
846 WAIT_FOR_MORE_GOALS: while($more_goals) {
847 READ_GOAL: while(my $goal = $self->{'goals_to_check_dict'}->iterate) {
848 if ($self->is_goal_in_our_facts($goal)) {
849 $self->{'viewer'}->debug("The goal $goal is in our facts")
850 if $self->{'debug'};
851 # Matches with any visiited rule?
852 my $rule_no = $self->{'goals_to_check_dict'}->get_value(
853 $goal, 'rule');
854 # Take out this goal so we don't end with an infinite loop
855 $self->{'viwer'}->debug("Removing $goal from goals to check")
856 if $self->{'debug'};
857 $self->{'goals_to_check_dict'}->remove($goal);
858 # Update the iterator
859 $self->{'goals_to_check_dict'}->populate_iterable_array();
860 # no more goals, what about rules?
861 if ($self->{'visited_rules'}->size() eq 0) {
862 $self->{'viewer'}->debug("No more goals to read")
863 if $self->{'verbose'};
864 $more_goals = 0;
865 next WAIT_FOR_MORE_GOALS;
866 }
867 if (defined $rule_no) {
868 my $causes_total = $self->{'visited_rules'}->get_value(
869 $rule_no, 'causes_total');
870 my $causes_pending = $self->{'visited_rules'}->get_value(
871 $rule_no, 'causes_pending');
872 if (defined $causes_total and defined $causes_pending) {
873 # No more pending causes for this rule, lets shoot it
874 if ($causes_pending-1 le 0) {
875 my $last_rule = $self->remove_last_visited_rule();
876 if ($last_rule eq $rule_no) {
877 $self->{'viewer'}->debug("Going to shoot $last_rule")
878 if $self->{'debug'};
879 $self->shoot($last_rule, 'backward');
880 } else {
881 $self->{'viewer'}->print_error(
882 "Seems the rule ($rule_no) of goal " .
883 "$goal is not the same as the last " .
884 "visited rule ($last_rule)");
885 $more_goals = 0;
886 next WAIT_FOR_MORE_GOALS;
887 }
888 } else {
889 $self->{'visited_rules'}->update($rule_no,
890 {
891 causes_pending => $causes_pending-1
892 });
893 }
894 }
895 }
896 # How many objetives we have? if we are zero then we are done
897 if ($self->{'goals_to_check_dict'}->size() lt 0) {
898 $more_goals = 0;
899 } else {
900 $more_goals = 1;
901 }
902 # Re verify if there are more goals to check
903 next WAIT_FOR_MORE_GOALS;
904 } else {
905 # Ugh, the fact is not in our inference facts or asked facts,
906 # well, lets find the rule where this fact belongs
907 my $rule_of_goal = $self->get_rule_by_goal($goal);
908 if (defined $rule_of_goal) {
909 $self->{'viewer'}->debug("Found a rule with $goal as a goal")
910 if $self->{'debug'};
911 # Causes of this rule
912 my $rule_causes = $self->get_causes_by_rule($rule_of_goal);
913 # Copy the causes of this rule to our goals to check
914 $self->copy_to_goals_to_check($rule_of_goal, $rule_causes);
915 # We just *visited* this rule, lets check it
916 $self->visit_rule($rule_of_goal, $rule_causes->size());
917 # and yes.. we have more goals to check!
918 $self->{'goals_to_check_dict'}->populate_iterable_array();
919 $more_goals = 1;
920 next WAIT_FOR_MORE_GOALS;
921 } else {
922 # Ooops, lets ask about this
923 # We usually get to this case when any of the copied causes
924 # does not exists as a goal in any of the rules
925 my $answer = $self->ask_about($goal);
926 if (
927 $answer eq FACT_SIGN_POSITIVE or
928 $answer eq FACT_SIGN_NEGATIVE) {
929 $self->{'asked_facts'}->append($goal,
930 {
931 name => $goal,
932 sign => $answer,
933 algorithm => 'backward'
934 });
935 } else {
936 $self->{'viewer'}->debug(
937 "Don't know of $goal, nothing else to check"
938 );
939 return 0;
940 }
941 $self->{'goals_to_check_dict'}->populate_iterable_array();
942 $more_goals = 1;
943 next WAIT_FOR_MORE_GOALS;
944 }
945 }
946 }
947 }
948 return 1;
949 }
950  
951 =head2 B<mixed()>
952  
953 As its name says, it's a mix of L<forward()> and L<backward()> algorithms, it
954 requires to have at least one initial fact.
955  
956 The first thing it does is to run the L<forward()> algorithm (hence the need of
957 at least one initial fact). If the algorithm fails then the mixed algorithm
958 also ends unsuccessfully.
959  
960 Once the first I<run> of L<forward()> algorithm happens it starts looking for
961 any positive inference fact, if only one is found then this ends the algorithm
962 with the assumption it knows what's happening.
963  
964 In case no positive inference fact is found then it will start reading the
965 rules and creating a list of intuitive facts.
966  
967 For each rule it will get a I<certainty factor> of its causes versus the
968 initial, inference and asked facts. In case the certainity factor is greater or
969 equal than L<found_factor> then all of its goals will be copied to the
970 intuitive facts (eg, read it as: it assumes the goals have something to do with
971 our first initial facts).
972  
973 Once all the rules are read then it verifies if there are intuitive facts, if
974 no facts are found then it ends with the intuition, otherwise it will run the
975 L<backward()> algorithm for each one of these facts (eg, each fact will be
976 converted to a goal). After each I<run> of the L<backward()> algorithm it will
977 verify for any positive inference fact, if just one is found then the algorithm
978 ends.
979  
980 At the end (if there are still no positive inference facts) it will run the
981 L<forward()> algorithm and restart (by looking again for any positive inference
982 fact).
983  
984 A good example to understand how this algorithm is useful is: imagine you are
985 a doctor and know some of the symptoms of a patient. Probably with the first
986 symptoms you have you can get to a positive conclusion (eg that a patient has
987 I<X> disease). However in case there's still no clue, then a set of questions
988 (done by the call of L<backward()>) of symptons related to the initial symptoms
989 will be asked to the user. For example, we know that that the patient has a
990 headache but that doesn't give us any positive answer, what if the patient has
991 flu or another disease? Then a set of these I<related> symptons will be asked
992 to the user.
993  
994 =cut
995 sub mixed {
996 my ($self) = @_;
997  
998 if (!$self->forward()) {
999 $self->{'viewer'}->print_error("The first execution of forward failed");
1000 return 0;
1001 }
1002  
1003 use Data::Dumper;
1004  
1005 while(1) {
1006 # We are satisfied if only one inference fact is positive (eg, means we
1007 # got to our result)
1008 while(my $fact = $self->{'inference_facts'}->iterate) {
1009 my $sign = $self->{'inference_facts'}->get_value($fact, 'sign');
1010 if ($sign eq FACT_SIGN_POSITIVE) {
1011 $self->{'viewer'}->debug(
1012 "We are done, a positive fact was found"
1013 );
1014 return 1;
1015 }
1016 }
1017  
1018 my $intuitive_facts = AI::ExpertSystem::Advanced::Dictionary->new(
1019 stack => []);
1020  
1021 my ($more_rules, $current_rule) = (1, undef);
1022 while($more_rules) {
1023 $current_rule = $self->{'knowledge_db'}->get_next_rule($current_rule);
1024  
1025 # No more rules?
1026 if (!defined $current_rule) {
1027 $self->{'viewer'}->debug("We are done with all the rules, bye")
1028 if $self->{'verbose'};
1029 $more_rules = 0;
1030 last;
1031 }
1032  
1033 # Wait, we already shot this rule?
1034 if ($self->is_rule_shot($current_rule)) {
1035 $self->{'viewer'}->debug("We already shot rule: $current_rule")
1036 if $self->{'verbose'};
1037 next;
1038 }
1039  
1040 my $factor = $self->get_causes_match_factor($current_rule);
1041 if ($factor ge $self->{'found_factor'} && $factor lt 1.0) {
1042 # Copy all of the goals (usually only one) of the current rule to
1043 # the intuitive facts
1044 my $goals = $self->get_goals_by_rule($current_rule);
1045 while(my $goal = $goals->iterate_reverse) {
1046 $intuitive_facts->append($goal,
1047 {
1048 name => $goal,
1049 sign => $goals->get_value($goal, 'sign')
1050 });
1051 }
1052 }
1053 }
1054 if ($intuitive_facts->size() eq 0) {
1055 $self->{'viewer'}->debug("Done with intuition") if
1056 $self->{'verbose'};
1057 return 1;
1058 }
1059
1060 $intuitive_facts->populate_iterable_array();
1061  
1062 # now each intuitive fact will be a goal
1063 while(my $fact = $intuitive_facts->iterate) {
1064 $self->{'goals_to_check_dict'}->append(
1065 $fact,
1066 {
1067 name => $fact,
1068 sign => $intuitive_facts->get_value($fact, 'sign')
1069 });
1070 $self->{'goals_to_check_dict'}->populate_iterable_array();
1071 print "Running backward for $fact\n";
1072 if (!$self->backward()) {
1073 $self->{'viewer'}->debug("Backward exited");
1074 return 1;
1075 }
1076 # Now we have inference facts, anything positive?
1077 $self->{'inference_facts'}->populate_iterable_array();
1078 while(my $inference_fact = $self->{'inference_facts'}->iterate) {
1079 my $sign = $self->{'inference_facts'}->get_value(
1080 $inference_fact, 'sign');
1081 if ($sign eq FACT_SIGN_POSITIVE) {
1082 $self->{'viewer'}->print(
1083 "Done, a positive inference fact found"
1084 );
1085 return 1;
1086 }
1087 }
1088 }
1089 $self->forward();
1090 }
1091 }
1092  
1093 =head2 B<summary($return)>
1094  
1095 The main purpose of any expert system is the ability to explain: what is
1096 happening, how it got to a result, what assumption(s) it required to make,
1097 the fatcs that were excluded and the ones that were used.
1098  
1099 This method will use the L<viewer> (or return the result) in YAML format of all
1100 the rules that were shot. It will explain how it got to each one of the causes
1101 so a better explanation can be done by the L<viewer>.
1102  
1103 If C<$return> is defined (eg, it got any parameter) then the result wont be
1104 passed to the L<viewer>, instead it will be returned as a string.
1105  
1106 =cut
1107 sub summary {
1108 my ($self, $return) = @_;
1109  
1110 # any facts we found via inference?
1111 if (scalar @{$self->{'inference_facts'}->{'stack'}} eq 0) {
1112 $self->{'viewer'}->print_error("No inference was possible");
1113 } else {
1114 my $summary = {};
1115 # How the rules started being shot?
1116 my $order = 1;
1117 # So, what rules we shot?
1118 foreach my $shot_rule (sort(keys %{$self->{'shot_rules'}})) {
1119 $summary->{'rules'}->{$shot_rule} = {
1120 order => $order,
1121 };
1122 $order++;
1123 # Get the causes and goals of this rule
1124 my $causes = $self->get_causes_by_rule($shot_rule);
1125 $causes->populate_iterable_array();
1126 while(my $cause = $causes->iterate) {
1127 # How we got to this cause? Is it an initial fact,
1128 # an inference fact? or by forward algorithm?
1129 my ($method, $sign, $algorithm);
1130 if ($self->{'asked_facts'}->find($cause)) {
1131 $method = 'Question';
1132 $sign = $self->{'asked_facts'}->get_value($cause, 'sign');
1133 $algorithm = $self->{'asked_facts'}->get_value($cause, 'algorithm');
1134 } elsif ($self->{'inference_facts'}->find($cause)) {
1135 $method = 'Inference';
1136 $sign = $self->{'inference_facts'}->get_value($cause, 'sign');
1137 $algorithm = $self->{'inference_facts'}->get_value($cause, 'algorithm');
1138 } elsif ($self->{'initial_facts_dict'}->find($cause)) {
1139 $method = 'Initial';
1140 $sign = $self->{'initial_facts_dict'}->get_value($cause, 'sign');
1141 } else {
1142 $method = 'Forward';
1143 $sign = $causes->get_value($cause, 'sign');
1144 }
1145 $summary->{'rules'}->{$shot_rule}->{'causes'}->{$cause} = {
1146 method => $method,
1147 sign => $sign,
1148 algorithm => $algorithm,
1149 };
1150 }
1151  
1152 my $goals = $self->get_goals_by_rule($shot_rule);
1153 $goals->populate_iterable_array();
1154 while(my $goal = $goals->iterate) {
1155 # We got to this goal by asking the user of it? or by
1156 # "natural" backward algorithm?
1157 my ($method, $sign, $algorithm);
1158 if ($self->{'asked_facts'}->find($goal)) {
1159 $method = 'Question';
1160 $sign = $self->{'asked_facts'}->get_value($goal, 'sign');
1161 } elsif ($self->{'inference_facts'}->find($goal)) {
1162 $method = 'Inference';
1163 $sign = $self->{'inference_facts'}->get_value($goal, 'sign');
1164 $algorithm = $self->{'inference_facts'}->get_value($goal, 'algorithm');
1165 } else {
1166 $method = 'Backward';
1167 $sign = $goals->get_value($goal, 'sign');
1168 }
1169 $summary->{'rules'}->{$shot_rule}->{'goals'}->{$goal} = {
1170 method => $method,
1171 sign => $sign,
1172 algorithm => $algorithm,
1173 }
1174 }
1175 }
1176 my $yaml_summary = Dump($summary);
1177 if (defined $return) {
1178 return $yaml_summary;
1179 } else {
1180 $self->{'viewer'}->explain($yaml_summary);
1181 }
1182 }
1183 }
1184  
1185 # No need to document this, this is an *internal* Moose method, used when an
1186 # instance of the class has been created and all the verifications (of valid
1187 # parameters) have been done.
1188 sub BUILD {
1189 my ($self) = @_;
1190  
1191 if (!defined $self->{'viewer'}) {
1192 if (defined $self->{'viewer_class'}) {
1193 $self->{'viewer'} = AI::ExpertSystem::Advanced::Viewer::Factory->new(
1194 $self->{'viewer_class'});
1195 } else {
1196 confess "Sorry, provide a viewer or a viewer_class";
1197 }
1198 }
1199 $self->{'initial_facts_dict'} = AI::ExpertSystem::Advanced::Dictionary->new(
1200 stack => $self->{'initial_facts'});
1201 $self->{'inference_facts'} = AI::ExpertSystem::Advanced::Dictionary->new;
1202 $self->{'asked_facts'} = AI::ExpertSystem::Advanced::Dictionary->new;
1203 $self->{'goals_to_check_dict'} = AI::ExpertSystem::Advanced::Dictionary->new(
1204 stack => $self->{'goals_to_check'});
1205 $self->{'visited_rules'} = AI::ExpertSystem::Advanced::Dictionary->new(
1206 stack => []);
1207 }
1208  
1209 =head1 SEE ALSO
1210  
1211 Take a look L<AI::ExpertSystem::Simple> too.
1212  
1213 =head1 AUTHOR
1214
1215 Pablo Fischer (pablo@pablo.com.mx).
1216  
1217 =head1 COPYRIGHT
1218
1219 Copyright (C) 2010 by Pablo Fischer.
1220
1221 This library is free software; you can redistribute it and/or modify
1222 it under the same terms as Perl itself.
1223  
1224 =cut
1225  
1226 1;
1227