Q3Artificial Intelligence Techniques

Characteristics of Knowledge Representation

• Representational adequacy: the knowledge representation scheme must be capable of correctly and completely capturing all the different types of knowledge actually required for the given problem domain, without losing essential information needed for correct reasoning.
• Inferential adequacy: the representation must support the ability to manipulate the represented knowledge to derive new knowledge or conclusions that logically follow from the existing represented facts, enabling the reasoning process central to any intelligent system.
• Inferential efficiency: beyond merely supporting inference in principle, a good representation should allow this inference process to be carried out efficiently, incorporating additional structural information or heuristics that help direct the reasoning process toward relevant conclusions without excessive computational overhead.
• Acquisitional efficiency: the representation scheme should support convenient and efficient acquisition of new knowledge, whether through direct manual encoding by a knowledge engineer or automated learning from data or experience, minimizing the effort and complexity involved in expanding the knowledge base over time.

Properties of Knowledge

• Declarative vs procedural knowledge: declarative knowledge represents facts and relationships about the world (stating what is true), while procedural knowledge represents specific methods or procedures for accomplishing a task (stating how to do something) — a complete knowledge representation system typically needs to capture both forms.
• Structured (hierarchical/organized) knowledge: knowledge is often naturally organized into hierarchical or networked structures (such as class-subclass relationships, part-whole relationships, or causal chains), and an effective representation scheme should be able to capture and exploit this inherent structure for more efficient storage and reasoning.
• Heuristic knowledge: in addition to certain, verified facts, much practical knowledge (particularly expert knowledge) consists of heuristic rules of thumb, learned through experience, that are generally reliable but not logically guaranteed, and a good knowledge representation should be able to appropriately capture and reason with this uncertain, heuristic form of knowledge alongside strictly certain facts.
• Incompleteness and uncertainty: real-world knowledge is frequently incomplete or uncertain, and a robust knowledge representation scheme should provide some mechanism (such as probabilistic reasoning, fuzzy logic, or default/non-monotonic reasoning) for representing and reasoning appropriately under this inherent incompleteness and uncertainty, rather than requiring all represented knowledge to be perfectly certain and complete.

Hill Climbing Algorithm - Step by Step Procedure

Hill climbing is a local search optimization algorithm that iteratively attempts to improve a current candidate solution by making small, incremental changes, always moving toward a neighboring state that offers a better value of a given evaluation (objective) function, and continuing until no further improving neighboring state can be found.

• Step 1: evaluate the initial current state using the problem's evaluation (heuristic/objective) function, and set this as the current best state found so far.
• Step 2: generate all (or a representative sample of) neighboring states reachable from the current state by applying a single available operator/move.
• Step 3: evaluate each generated neighboring state using the evaluation function.
• Step 4: select the neighboring state with the best (highest, for a maximization problem) evaluation-function value among all generated neighbors.
• Step 5: if this best neighboring state has a strictly better evaluation-function value than the current state, move to that neighboring state (making it the new current state), and return to Step 2 to continue the search from this new position.
• Step 6: if none of the generated neighboring states offers an improvement over the current state's own evaluation-function value (i.e., the current state is a local maximum with respect to its immediate neighbors), terminate the algorithm and return the current state as the final solution found.

Key limitation: because hill climbing only ever considers immediate neighboring states and always moves toward the locally best-appearing option, it is inherently susceptible to becoming permanently stuck at a local maximum (a state better than all its immediate neighbors, but not the best possible state, i.e., not the true global maximum, in the overall search space) — hill climbing also frequently struggles with plateaus (regions where many neighboring states share the same evaluation value, providing no clear improving direction to follow) and ridges (narrow regions of high value oriented such that no single-step move directly follows the ridge's direction), limitations that have motivated various enhanced variants of the basic algorithm, including stochastic hill climbing (randomly selecting among improving moves rather than always the single best one), random-restart hill climbing (repeating the search from multiple different randomly-chosen initial states to increase the chance of finding the true global maximum), and simulated annealing (occasionally accepting a worse-evaluated move, with a probability that decreases over time, specifically to help escape local maxima that a purely greedy hill-climbing search would otherwise become permanently trapped within).

It is also worth noting that the choice of search strategy for a given problem is heavily influenced by the specific characteristics of its state space (its branching factor, depth, and whether a suitable heuristic function is available), and that in practice, many real-world AI planning and problem-solving systems combine multiple search techniques (for example, using an informed heuristic search for the bulk of the search while falling back on more exhaustive uninformed search only in regions of the state space where no useful heuristic guidance is available) rather than relying on a single pure search strategy throughout.

Hill climbing, while computationally simple and often effective for well-behaved optimization landscapes, is well known to suffer from several characteristic failure modes: it can become permanently trapped at a local maximum (a state better than all its immediate neighbors but not the true global optimum), a plateau (a flat region of the search space where all neighboring states have identical evaluation, providing no directional guidance), or a ridge (a sequence of local maxima that cannot be traversed by considering only single-step neighbor moves), motivating various enhancements such as random-restart hill climbing (running the basic algorithm repeatedly from different randomly-chosen starting states) or simulated annealing (occasionally accepting a worse move with a probability that decreases over time, allowing the search to escape local optima that pure hill climbing cannot).

These enhancements to basic hill climbing illustrate a recurring theme in AI search: balancing computational simplicity against robustness to the many pitfalls that a naive greedy local-search strategy can encounter on a realistically complex search landscape.