Design and Applications of a Generic and 
              Heuristic Problem Solver

Contents

Abstract

Example

Design

Educational Goals and Applications

Current Work

Abstract

webSolutions www.webmath.ch  is a web Mathematica programming project of the Swiss Distance University of Applied Sciences which deals with the development and deployment of detailed, dynamic and interactive step-by-step solutions to mathematical problems.

The subproject Generic is dedicated to the development of a generic and heuristic step-by-step solver. 
The design of the search algorithm is a heuristic best-first search providing parameters for general stop conditions (depth, breadth, number of computed expressions and time), parameters for complexity (also including a functional parameter for heuristic functions), parameters for the mathematical context (e.g. rules) and display parameters for the formatting and styling of the output.

The core parts of the subproject are Mathematica programs implementing techniques of a heuristic best-first search. Java Server Pages and webMathematica are widely used to deploy the results to the World Wide Web.

The presentation covers the design and educational applications of a generic and heuristic algorithm allowing the generation of step-by-step solutions to rule-based mathematical problems.

Example

Partial derivatives

f[Sin[a], a]

Such problems may be solved by a rule-based heuristic best-first search. It is possible to implement these methods on a computer ...

... and to deploy a Step-by-Step Solution in the World Wide Web. Hereby the technology of webMathematica  is very useful.

Design of a generic Step-by-Step Solver I

A lot of mathematical problems may be solved by repeated and careful application of transformation rules to expressions.

Typical examples are solving systems of linear equations, solving linear optimization problems, finding limits of functions, computing derivatives or integrals and simplifying mathematical expressions.

A generic algorithm should make use of the functionalities and principles of the underlying mathematical expert system to the widest possible extent ...

... and it should be usable in different mathematical contexts by providing parameters for transformation rules, additional rule-conditions, heuristic functions and rules for formatting and styling the output, as well as by providing parameters allowing to influence the program run.

The well-known design of a heuristic best-first-search is an appropriate approach to such a generic algorithm.

Design of a generic Step-by-Step Solver II (Parameters)

Four numeric parameters bounding the depth, breadth, number of computed expressions and computing time of searching (seconds).
Example: GeneralStopConditions = {10, Infinity, Infinity, 120}

The purpose of pre-functions or post-functions is to do things before or after the beginning or end of the problem solving procedure. Parsing or restructuring input expressions and setting or clearing attributes (commutativity, associativity, ... ) for mathematical operators are typical tasks of these functions.
Example 1 (partial derivatives):

PreFunctions:= {
   Module[{UnFlatteningRules},
      ClearAttributes[{Plus,Times},Flat];
      UnFlatteningRules=
        {f_ g_ h_ x___ :>((f g)h) x,
         f_+g_+h_+x___:>((f+g)+h)+x};
      ProblemExpression=ProblemExpression//.UnFlatteningRules;
   ];
   Module[{ff,xx},
      Clear[d];ff=ProblemExpression[[1]];xx=ProblemExpression[[2]];
      ProblemExpression=d[ff,xx]
   ];
   SetOptions[FreeQ,Heads->False];
   Off[Inner::heads];
};

The Problem Expression {f[Sin[a],a+b+c],a} would be transformed to d[f[Sin[a],(a+b)+c],a].

PostFunctions:={SetAttributes[{Times,Plus},Flat],
    SetOptions[FreeQ,Heads->True],On[Inner::heads]};

Example 2 (Boolean simplification):

PreFunctions:= {}; PostFunctions:={};

Five functional parameters for generally ordering expressions (1), ordering the transformation rules (2 & 3), bounding the complexity of expressions (4) and heuristic evaluation (strategy) of expressions (5) during the program run.
Example 1 (partial derivatives):

ComplexityFunctions := 
{ LeafCount, Null, Null, (True)&, (Infinity)& }

Example 2 (Boolean simplification)

ComplexityFunctions := 
{ LeafCount, Null, LeafCount, (True)&, (LeafCount)& }

Four functional parameters for computing a proposal solution (1), defining conditions for expressions to be accepted as solutions (2), comparing expressions to the proposed solution (3) and comparing expressions among themselves (4).
Example 1 (partial derivatives):

ProposedSolutions:={
    {(Module[{sol,UnFlatteningRules},
            SetAttributes[{Times,Plus},Flat];
            sol=Apply[D,#];
            ClearAttributes[{Times,Plus},Flat];
            UnFlatteningRules=
              {f_ g_ h_ x___ :>((f g)h) x,
                f_+g_+h_+x___:>((f+g)+h)+x};
            sol=sol//.UnFlatteningRules
      ])&
    },
    {(FreeQ[#,d,Heads->True])&},{SameQ},{SameQ}
};

Example 2 (Boolean Simplification):

ProposedSolutions:={
    {(FullSimplify[#,ComplexityFunction->ComplexityFunctions[[1]]])&},,
    {},{SameQ },{SameQ}
};

Design of a generic Step-by-Step Solver III
          (cont. Parameters: Rules)

List of extendend transformation rules. 
Each rule contains four parts: Mathematical transformation rule, additional conditions on rules, rule names and explanations describing the rule.
Sample 1 (partial derivatives): 5 of 16

ExtendedTransformationRules:={

{{d[c_, x_] :> 
                      0 /; Hold[FreeQ[c, x]]},{},{"Constant Rule"},{"The derivative of a constant is equal to zero."}},

{{d[x_, x_] :> 1},{},{"Identity rule"},{"The derivative of the identity function is the \
constant 1."}},

{{\(d[x_\^a_, x_] :> 
                      a\ x\^\(a - 1\) /; 
                        Hold[FreeQ[a, 
                              x]\  && \ \((a =!= 1)\) && \((a =!= 0)\)]\)},{},{"Power Rule"},{StringForm[
                    "The derivative of `` is equal to `` if a is independent \
of the variable ``.", TraditionalForm[(x^a)], 
                    TraditionalForm[a (x^(a - 1))], TraditionalForm[x]]}},

{{d[f_ + g_, x_] :> 
                      d[f, x] + d[g, x] /; 
                        Hold[(f =!= 
                                g) && (! FreeQ[f, x,  
                                    Heads -> False] || ! FreeQ[g, x,  
                                    Heads -> False])]},{},{"Addition rule"},{"The derivative of a sum is equal to the sum of the \
derivatives."}},

{{d[c_ f_, x_] :> 
                      c d[f, x] /; 
                        Hold[FreeQ[c, 
                              x] && ! FreeQ[f, x,  Heads -> False]]},{},{"Linear factor rule"},{StringForm[
                    "The derivative is proportional if the constant is \
independent of the variable ``.", TraditionalForm[x]]}}
}

Parameters for Rules (cont.)

Sample 2 (Boolean Simplification): 4 of 48

ExtendedTransformationRules:={
  {{And[x___,(f_&&(f_||g_)),y___]:> And[x,f,y]},{},{"Absorption"},
  {"𝔞 ∧ (𝔞 ∨ 𝔟) = 𝔞"}},
  {{Or[x___,(f_&&(f_||g_)),y___]:> Or[x,f,y]},{},{"Absorption"},
  {"𝔞 ∧ (𝔞 ∨ 𝔟) = 𝔞"}},
  {{And[x___,(f_||(f_&&g_)),y___]:> And[x,f,y]},{},{"Absorption"},
  {"𝔞 ∨ (𝔞 ∧ 𝔟) = 𝔞"}},
  {{Or[x___,(f_||(f_&&g_)),y___]:> Or[x,f,y]},{},{"Absorption"},
  {"𝔞 ∨ (𝔞 ∧ 𝔟) = 𝔞"}}}

Design of a generic Step-by-Step Solver IV
          (cont. Parameters: Formats and Layout)

Example 1 (partial derivatives): Standard notation

ExpressionFormattingRules := {
{d[p_, 
                  x_] :> 
                StringForm["\!\(`1`\/\(`2`\\ `3`\)\)(``)", "\[PartialD]", 
                  "\[PartialD]", x, StandardForm[p]]}, {x_ :> 
                StandardForm[x]}, {Inner -> 
                InnerRenamed}, {InnerRenamed[f_, l1_, l2_, 
                  g_] :>  StringForm["`1`.`2`",  l1, l2]}};

Example 2 (Boolean simplification): Traditional notation

ExpressionFormattingRules := 
{{Or[x_, 
                  y_] :> TraditionalForm[x || y],  
              And[x_, y_] :> TraditionalForm[x && y], 
              Not[x_] :> TraditionalForm[! x]}};

Example 1 (partial derivatives): Standard notation

RuleFormattingRules := {{d[p_, x_] :> 
                StringForm["\!\(`1`\/\(`2`  `3`\)\)(``)", "\[PartialD]", 
                  "\[PartialD]", x, StandardForm[p]]}, {a -> α, 
              f -> 𝒻, g -> ℊ, 
              c -> 𝒸}};

Example 2 (Boolean simplification): Traditional notation

RuleFormattingRules := {{f -> 𝔞, 
              g -> 𝔟, 
              h -> 𝔠}, {Or[x_, y_] :> 
                TraditionalForm[x || y], 
              And[x_, y_] :> TraditionalForm[x && y], 
              Not[x_] :> TraditionalForm[! x]}};

Among other things it is possible to style the layout of the transformed parts of expressions.

Example 1 (partial derivatives):

"Vector derivative rule: Partial derivative of a vector is computed by partial derivation of its components."
" "
"   \!\(\*TagBox[\(StandardForm\`\*StyleBox[\"\\\"\\\\!\\\\({\\\\(\\\\(\\\\(\\\\(\\\\*SuperscriptBox[\\\\\\\"f\\\\\\\", TagBox[\\\\((1, 0)\\\\), Derivative], Rule[MultilineFunction, None]]\\\\)\\\\)[\\\\(\\\\(\\\\(\\\\(Sin[a]\\\\)\\\\), a\\\\)\\\\)]\\\\)\\\\), \\\\(\\\\(\\\\(\\\\(\\\\*SuperscriptBox[\\\\\\\"f\\\\\\\", TagBox[\\\\((0, 1)\\\\), Derivative], Rule[MultilineFunction, None]]\\\\)\\\\)[\\\\(\\\\(\\\\(\\\\(Sin[a]\\\\)\\\\), a\\\\)\\\\)]\\\\)\\\\)}\\\\).\\\\!\\\\(\\\\*StyleBox[\\\\\\\"\\\\\\\\\\\\\\\"\\\\\\\\\\\\\\\\!\\\\\\\\\\\\\\\\(∂\\\\\\\\\\\\\\\\/\\\\\\\\\\\\\\\\(∂\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\ \\\\\\\\\\\\\\\\!\\\\\\\\\\\\\\\\(a\\\\\\\\\\\\\\\\)\\\\\\\\\\\\\\\\)\\\\\\\\\\\\\\\\)(\\\\\\\\\\\\\\\\!\\\\\\\\\\\\\\\\(\\\\\\\\\\\\\\\\*TagBox[\\\\\\\\\\\\\\\\(StandardForm\\\\\\\\\\\\\\\\`\\\\\\\\\\\\\\\\({\\\\\\\\\\\\\\\\(\\\\\\\\\\\\\\\\(Sin[a]\\\\\\\\\\\\\\\\)\\\\\\\\\\\\\\\\), a}\\\\\\\\\\\\\\\\)\\\\\\\\\\\\\\\\), StandardForm, Rule[Editable, True]]\\\\\\\\\\\\\\\\))\\\\\\\\\\\\\\\"\\\\\\\", Rule[FontColor, RGBColor[1, 0, 0]], Rule[FontSize, \\\\\\\"12\\\\\\\"]]\\\\)\\\"\", Rule[FontSize, \"12\"]]\), StandardForm, Rule[Editable, True]]\) = \!\(\*TagBox[\(StandardForm\`\*StyleBox[\"\\\"\\\\!\\\\({\\\\(\\\\(\\\\(\\\\(\\\\*SuperscriptBox[\\\\\\\"f\\\\\\\", TagBox[\\\\((1, 0)\\\\), Derivative], Rule[MultilineFunction, None]]\\\\)\\\\)[\\\\(\\\\(\\\\(\\\\(Sin[a]\\\\)\\\\), a\\\\)\\\\)]\\\\)\\\\), \\\\(\\\\(\\\\(\\\\(\\\\*SuperscriptBox[\\\\\\\"f\\\\\\\", TagBox[\\\\((0, 1)\\\\), Derivative], Rule[MultilineFunction, None]]\\\\)\\\\)[\\\\(\\\\(\\\\(\\\\(Sin[a]\\\\)\\\\), a\\\\)\\\\)]\\\\)\\\\)}\\\\).\\\\!\\\\(\\\\*StyleBox[\\\\({\\\\\\\"\\\\\\\\!\\\\\\\\(\\\\\\\\[PartialD]\\\\\\\\/\\\\\\\\(\\\\\\\\[PartialD]\\\\\\\\\\\\\\\\ \\\\\\\\!\\\\\\\\(a\\\\\\\\)\\\\\\\\)\\\\\\\\)(\\\\\\\\!\\\\\\\\(\\\\\\\\*TagBox[\\\\\\\\(StandardForm\\\\\\\\`\\\\\\\\(Sin[a]\\\\\\\\)\\\\\\\\), StandardForm, Rule[Editable, True]]\\\\\\\\))\\\\\\\", \\\\\\\"\\\\\\\\!\\\\\\\\(\\\\\\\\[PartialD]\\\\\\\\/\\\\\\\\(\\\\\\\\[PartialD]\\\\\\\\\\\\\\\\ \\\\\\\\!\\\\\\\\(a\\\\\\\\)\\\\\\\\)\\\\\\\\)(\\\\\\\\!\\\\\\\\(\\\\\\\\*TagBox[\\\\\\\\(StandardForm\\\\\\\\`a\\\\\\\\), StandardForm, Rule[Editable, True]]\\\\\\\\))\\\\\\\"}\\\\), Rule[FontColor, RGBColor[1, 0, 0]], Rule[FontSize, \\\\\\\"12\\\\\\\"]]\\\\)\\\"\", Rule[FontSize, \"12\"]]\), StandardForm, Rule[Editable, True]]\)"

Example 2 (Boolean simplification):

({{"Absorption: 𝔞 ∨ (𝔞 ∧ 𝔟) = 𝔞"}, {" "}, {"   \!\(\* StyleBox[ TagBox[ FormBox[ RowBox[{\((a ∨ b ∧ c ∨ ¬ d)\), \"∧\",  RowBox[{\"(\",  StyleBox[\(d ∨ a ∨ a ∧ ¬ b ∧ ¬ c\),\nFontWeight->\"Bold\",\nFontSlant->\"Italic\",\nFontColor->RGBColor[1, 0, 0]], \")\"}]}], \"TraditionalForm\"], TraditionalForm, Editable->True],\nFontSize->12]\) = \!\(\* StyleBox[ TagBox[ FormBox[ RowBox[{\((a ∨ b ∧ c ∨ ¬ d)\), \"∧\",  RowBox[{\"(\",  StyleBox[\(d ∨ a\),\nFontWeight->\"Bold\",\nFontSlant->\"Italic\",\nFontColor->RGBColor[1, 0, 0]], \")\"}]}], \"TraditionalForm\"], TraditionalForm, Editable->True],\nFontSize->12]\)"}})

The search procedure returns a list consisting of the best solution, a flag (e.g. {0} ("proposed solution found")) and the history of applied rules, positions and corresponding partial results of partially transformed expressions.

{Derivative[0, 1][f][Sin[a], a]+Cos[a] Derivative[1, 0][f][Sin[a], a],{0},
{Derivative[0, 1][f][Sin[a], a]+Cos[a] Derivative[1, 0][f][Sin[a], a],{
{16,{},Inner[Times,{Derivative[1, 0][f][Sin[a], 
                                a],Derivative[0, 1][f][Sin[a], 
                                a]},d[{Sin[a], a}, a],Plus]},
{15, {3}, {d[Sin[a], a], d[a, a]}},
{4, {2, 1}, Cos[a]},
{2, {1, 1}, 1}}},6}

Educational Goals and Applications

Students learn and practise applying structured methods of solutions to concrete problems.

Students control and correct their own 'handwritten' solutions to exercises.

Tutors and students present, reprocess and communicate complex solutions in a simple electronic way.

Tutors have the possibility to add their own teaching material, to modify the existing material or to manipulate the running of the program fundamentally.

Current work (improvements)

Optimization of the Mathematica code.

Implementation of a database saving solutions patterns to problem patterns that have already been solved.

Solving systems of linear equations, linear optimization, computing limits of functions, 
symbolic integration ...

Development of a user-friendly and interactive Mathematica application supporting the parametrization process.

The user (student) is allowed to propose rules and interim or final results between the steps of the solution, ...

... to browse backwards and forwards through the separate steps, and ...

... to administrate several computations in parallel ...

... Example (prototypes): http://www.webmath.ch.