KR100402849B1 - System and method for spatial layout planning over the web - Google Patents

Abstract

Home space planning system and method in a web environment according to the present invention, in the home space planning, the data input module 32 that receives the user's requirements from the client side, and verifies whether the user requirements and constraints conflict Based on the constraint verification module 34, the knowledge base 50, the problem solving module 36 for deriving the final result, and the two-dimensional result output module 38 for outputting the result in two dimensions to the user. It includes a CSP problem solving engine 30 and VRML code generator 40 for outputting the two-dimensional results designed by the CSP problem solving engine 30 in three dimensions.

Therefore, in addition to automating the design of housing spaces, the remote users can directly experience the virtual homes according to their tastes through the web.

Description

Housing space planning system and method in web environment {SYSTEM AND METHOD FOR SPATIAL LAYOUT PLANNING OVER THE WEB}

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to spatial layout planning using a computer, and more specifically, to designing a residential space using a resource allocation method based on a CSP (Constraint Satisfaction Problems) solution. The present invention relates to a housing space planning system and method in a web environment that can meet the requirements of human resources.

In general, a spatial layout planning system (Spatial Layout Planning System) refers to a system that optimizes space efficiency by allocating rectangular resources in a certain space according to the user's needs and maximizing user satisfaction. These space planning problems generally tend to exponentially increase the search space and computation time as the two-dimensional space is larger and the number of resources increases. Therefore, the complexity of space planning needs to be explored over a large range of space. In addition, it must also be able to accommodate the user's dynamic requirements, such as specific areas of revision or redesign.

Housing space planning, one of the major problems of space planning, is the arrangement of resources in rectangular form of floor, bedroom, kitchen, etc. within limited housing space according to the relationship between each resource as well as the conditions desired by the user. . It has most of the difficulties in the space planning problem, and especially in terms of the optimization problem, it is difficult to define an optimal function that can represent the user satisfaction that shows a significant difference according to personal tendencies.

In order to solve the above problems, much research has been done in the past, and a methodology using a knowledge-based system has been proposed for the floor plan design problem using Prolog at Copenhagen University. . In addition, Tokyo Gas Corporation of Japan has developed a residential space design system using the CLP (Constraint Logic Programming) technique called Constraint Based Planner (CBP). However, these space planning systems not only take a lot of time due to the high complexity of the space planning problem, but also have a problem in that they do not produce a result that can satisfy the user's needs.

SUMMARY OF THE INVENTION The present invention has been made to overcome the above-mentioned conventional problems, and an object of the present invention is to satisfy a dynamic requirement of a user by designing a housing space using a resource allocation method based on a Constraint Satisfaction Problems (CSP) solution. It is also to provide a housing space planning system and method in a web environment that can minimize the time it takes to find solutions to housing space problems .

Another object of the present invention is to implement a residential space designed as a virtual reality system using the VRML (Virtual Reality Modeling Language) by providing a three-dimensional design drawings to the user to plan the housing space in a web environment intuitively and To provide a method.

The housing space planning system in a web environment according to the present invention for achieving the object of the present invention, a data input module that receives the user's requirements from the client side, and verifies whether the user requirements and constraints conflict The CSP problem solving engine and the CSP problem solving engine including a constraint verification module, a problem solving module for deriving a final result based on a knowledge base, and a two-dimensional result output module for outputting the result in two dimensions to a user. It includes a VRML code generator for outputting two-dimensional results designed in three dimensions.

1 is an overall configuration diagram of a housing space planning system in a web environment according to the present invention.

FIG. 2 is a diagram illustrating an internal module of the CSP problem solving engine of FIG. 1. FIG.

3 is a flowchart illustrating a housing space planning method in a web environment according to the present invention;

4 is an embodiment of housing space planning by the space division method.

5 is an embodiment of housing space planning by the resource allocation method.

6 is an embodiment when the shape of the housing space is not a rectangular shape.

Explanation of symbols on the main parts of the drawings

10: User 10A: Web Browser

20: server control unit 30: CSP problem solving engine

32: data input module 34: constraint verification module

36: troubleshooting module 38: two-dimensional output module

40: VRML code generator 50: Knowledge Base

60: local user 100: web server

Hereinafter, with reference to the accompanying drawings will be described in detail the present invention.

Referring to Figure 1, the overall configuration of the housing space planning system in a web environment according to the present invention is shown.

As shown, a plurality of users 10 who want to receive housing planning services through the Internet and a plurality of local users 60 who want to receive housing planning services through the Internet, and the user 10 have three-dimensional houses. Web browser 10A for outputting a space design drawing, a CSP problem solving engine 30 for performing a housing space design process according to constraints input from a user using a CSP technique, and the CSP problem solving engine 30 VRML code generator 40 for generating VRML code so that the user can view the two-dimensional design drawings designed through the 3D, and the knowledge base 50 for storing architectural knowledge through experts in the field of architectural design, and It consists of a server control unit 20 for controlling all configurations.

2 is a diagram illustrating an internal module of the CSP problem solving engine 30 of FIG. 1.

As shown, the CSP problem solving engine 30 is a data input module 32 that receives the user's requirements from the user (10, 60) side, constraints for verifying whether the user requirements and constraints conflict It consists of a verification module 34, a problem solving module 36 for deriving the final result based on the knowledge base 50, and a two-dimensional result output module 38 for outputting the result in two dimensions to the user. At this time, the data input module 32 receiving the user's requirements receives data and attributes of each resource, for example, a floor, a room, a kitchen, and the like. It accepts static constraints for dynamic constraints and dynamic constraints to accommodate user requirements.

3 is a flowchart illustrating a housing space planning method in a web environment according to the present invention.

As shown, the housing space planning method in the web environment according to the present invention is performed as follows.

First, the client 10, which is a client, accesses the Internet web server 100 through the web to receive the housing space planning service. The user 10 first inputs an attribute of a space desired by the user, an attribute of each room, a user requirement, and the like into the data input module 32 (S1).

The data entered in this way enters the constraint verification module 34 and is validated by the constraint (S2). At this time, if an error occurs due to a collision of constraints (S3), a correction message is shown to the user and a re-input is requested (S4).

On the other hand, the data passed through the constraint verification module 34 enters the problem solving module 36 and enters the task of solving the housing space problem (S5). At this time, the process of solving the housing space problem through the problem solving module 36 is satisfied whether the constraints according to the relationship between the resources and attributes such as location, size, direction of each resource, and user requirements and heuristics ( Heuristic).

When the solution of the housing space is solved as described above, the drawing of the housing space designed through the two-dimensional result output module 38 is output in two dimensions (S6).

Next, if there is no complaint of the user 10 with respect to the output two-dimensional design drawing (S7), and generates a VRML code through the VRML code generator 40 (S9), the user's web browser (10A) By sending the VRML code generated as to enable the user 10 to view the three-dimensional design drawings (S10).

Referring to Figure 3, the process of the housing space planning method based on the CSP solution technique in the web environment will be described in detail as follows.

In general, the methods for allocating rooms in a limited housing space include the Space Partitioning Method, which divides by drawing vertical and horizontal lines in two dimensions, and the resource allocation method, which fits while fitting a two-dimensional plane. Allocation Method).

Space partitioning method (Space Partitioning Method) is a method of recursively performing the operation of drawing a rectangular space with a vertical line and a horizontal line as shown in FIG. If the space is divided by the number of resources, each resource is placed. If the result is not satisfied, the result is checked. If it is not satisfied, the backtracking is performed until the satisfactory solution is obtained. It is.

Therefore, this method has a disadvantage in that it is impossible to determine whether a divided space is a space to which resources are to be mapped or a space to be divided again.

On the other hand, the resource allocation method (Resource Allocation Method) selects candidate resources to be placed in the two-dimensional space as shown in FIG. 5 and then checks the constraints of the resources. When the constraints are met, they are locked in place where they can be placed in the space. This task is repeated until all resources are deployable.

Thus, the distinction between resources and space is clear, and the components of the CSP are variables ( room coordinates, room width, room height ), domains ( room width, room height, room coordinates ), constraints ( room In the present invention, the relationship between the constraints according to the attributes, the constraints between the locations of the rooms, the constraints between the sizes of the rooms ) is similar to the relationship between the resources, the space in which the resources are located, and the constraints between the resources. Use the assignment method.

In resource allocation problems, the order in which resources are allocated can be a significant factor. This is because the resource allocation process shows a significant difference in domain filtration due to constraint propagation.

Heuristics for resource allocation order are shown in Table 1.

Assignment order based on resource size Assigned to the largest room Assigned to the smallest room first Assignment order based on resource allocation range Assign from room with large size range Assignment to a room with a small size range

Heuristic Types for Resource Allocation Order

In this case, heuristic refers to a method of finding the correct final solution by itself by repeating trial and error step by step, using a domain filtering technique through various Look-Ahead CSP solutions such as forward checking. By allocating a higher number first, the time taken to find a solution can be reduced efficiently by reducing the number of backtrackings.

Accordingly, the present invention allows the first room to be placed first by using a domain filtration technique through forward checking, so that the room can be placed first with a large area, thereby reducing the allocation space of the other room to the maximum, and the size range of the room. The larger the value, the greater the probability of multiple shapes coming out of one room, so the smaller the size range, the greater the priority. As described above, the present invention design a housing space using a resource allocation method based on the Constraint Satisfaction Problems (CSP) solution, but the resources (room, CSP modeling is performed with variables, domains, and constraints that are CSP components in order to arrange kitchens, bathrooms, and the like. Solve effectively. Hereinafter, the process of the housing space planning method based on the CSP solution technique in the web environment will be described in detail.

First, in step S1, the users 10 and 60 who access the Internet web server 100 through the web to receive the housing space planning service input the attributes and data of each resource. For example, specify the name of the housing space, the width and length of the space, and the direction, location, and size of the entrance.

Also, refer to [Table 2] to specify attributes such as bedrooms, bathrooms, surroundings such as walls, floors, kitchens open all around, and special rooms, such as entrances that are restricted by the location and size of entrances. And enter the constraints associated with each attribute.

space Surrounded by a wall Presence of position constraints Presence or absence of size constraints Proximity Constraints sewer mining Inner room O X O O Floor bedroom O X O O Floor, toilet restroom O O X O Floor, toilet Floor X X O O Bedroom, bedroom, toilet, kitchen Kitchen X O O O Floor

Classification by room property

At this time, the constraints are divided into two types: static constraints for geometric validity and dynamic constraints for accommodating user's requirements.

First of all, the static constraints are as follows. First, the location and length of the room are integer values. Since the CSP of the present invention has a problem solving ability for a finite discrete domain, The values assigned to the four corresponding variables have the form of integers.

Second, the sum of the room widths is equal to the size of the field, because no empty space should exist when the room is placed in a housing space.

Third, the location of the room can not be out of the field, because it is forbidden to leave the housing space when the room is placed in the housing space.

Fourth, each room does not overlap each other, because each room is located with a wall of constant thickness between them.

Dynamic constraints, on the other hand, include room size ranges, length ranges and position ranges and edge position settings, adjacency settings, and room settings according to particular attributes.

If lighting is required, such as on a bedroom or floor, or on an exterior wall, such as a veranda, the room must be located at the edge of the house space, which is subject to the constraints of the edge positioning and moves directly from one room to another. If it should be possible, for example, in the case of floors and backyards, the adjacency is a constraint.

In the case where the setting of rooms according to special properties is given as a constraint, stronger constraints than general room constraints are given according to the position and size of the entrance as in the case of the entrance.

Next, each constraint input by the user 10 and 60 in step S2 is verified for its suitability through the knowledge-based constraint verification module 34.

In S3 and S4, after the input of user requirements is completed, just before the start of troubleshooting, the constraints are checked for conflict and if they are not suitable, an error message is displayed to the user to reduce the time required to find unnecessary or impossible solutions. do.

In this case, the content of constraint collisions verified in the knowledge base is, for example, 'First, the minimum width of the room is 1 or more and less than the width of the floor.' Second, the sum of the minimum widths of the rooms is less than the width of the floor. ', Third, the sum of the maximum widths of the rooms is more than the width of the floor.' Fourth, there is only one room that represents the entrance property. Fifth, the minimum length of the room is one side of the floor. Limit to length or less. ',' Sixth, the range of minimum and maximum lengths of a room includes the possible lengths of the size limit of the room. ',' Seventh, the sum of the positional range limitation of the room and the minimum length limit of the room may be Limited to less than And the like.

Thereafter, the data passing the constraint verification module 34 in step S4 enters the problem solving module 36 in step S5 and starts to solve the housing space problem.

At this time, the optimal solution can be defined as the solution with the highest satisfaction according to the preferences of the users, but it is impossible to model different symbols for each individual and it is difficult to obtain an optimization function.

Therefore, the present invention takes a trial-and-error method as a method of improving the user's satisfaction. That is, it provides a solution that is assumed to be the best for the user and requires the user to modify the constraints. If the user is not satisfied with the best solution provided by the system, the dynamics of the constraints are determined by the interaction between the user and the system. The solution is to add, enhance, remove, or alleviate it repeatedly.

On the other hand, in a special case, for example, when it is necessary to arrange a room in a concave-convex housing space as shown in Fig. 6, after setting a house space of a size that can include all the concave-convex, add a room that can fill the empty space This can be solved by giving constraints on the position and size range. In addition, in the case where the lighting is possible through the ceiling of the house, it is solved by limiting the location range by setting the position of the room where the light is required, without limiting the position to the edge.

When the solution of the housing space problem is obtained in the step S5, the drawing of the housing space designed through the two-dimensional result output module 38 in the step S6 is output in two dimensions.

Next, in step S7 it is required to modify the constraints in order to increase the user's satisfaction with the output two-dimensional design drawings. By repeating this process, the convergence results in optimizing user satisfaction, reducing the time required, and obtaining a reasonable result in a realistic aspect.

Thereafter, if there is no complaint from the user 10, the VRML code is generated through the VRML code generator 40 in steps S8 to S10 and the VRML code generated by the user's web browser 10A is sent to the user ( 10) allow you to see the 3D design drawing. Therefore, the user 10 can more intuitively recognize the design drawing of the design of the completed housing space.

What has been described above is only one embodiment for implementing a housing space planning system and method in a web environment according to the present invention, the present invention is not limited to the above-described embodiment, it is claimed in the claims As will be apparent to those skilled in the art to which the present invention pertains without departing from the gist of the present invention, the technical spirit of the present invention may be changed to the extent that various modifications can be made.

As described above, the housing space planning system and method in the web environment according to the present invention is designed through the effective interaction technology with the user by designing the housing space using the resource allocation method based on the Constraint Satisfaction Problems (CSP) solution. Not only does it have the advantage of accommodating the various requirements of the user, it also has the outstanding effect of minimizing the time it takes to solve the housing space problem.

In addition, by using VRML (Virtual Reality Modeling Language), it extends to the web environment, providing users with 3D design drawings for intuitive recognition, and not only automating the design of housing space, It is effective to indirectly experience the right virtual home.

Claims (5)

Data input module 32 for receiving the user's requirements from the client side in the server / client environment, constraint verification module 34 for verifying whether the user requirements and constraints conflict, knowledge base 50 A problem solving engine 30 comprising a problem solving module 36 for deriving a final result based on the result, and a two-dimensional result output module 38 for outputting the result in two dimensions to a user; And a VRML code generator 40 for outputting a two-dimensional result designed through the problem solving engine 30 in three dimensions. The problem solving engine 30 uses a resource allocation method based on the CSP (Constraint Satisfaction Problems) solving method to design a housing space according to a requirement input from a user. Space planning system. The method of claim 1, wherein the resource allocation method based on the CSP resolution technique, Variables (room coordinates, room width, height of the room), domain (room width of the room) of the CSP components for the placement of various sizes of resources (room, kitchen, toilet, etc.) to meet user requirements in a limited sized housing space. Perform CSP modeling with range, range of room height, range of room coordinates, and constraints (constraints based on room properties, constraints between room locations, constraints between room sizes), and forward checking. Housing space planning system in a web environment, using the various look-ahead CSP solutions, such as to solve the housing space problem. Receiving a user requirement from a user 10 connected to the Internet web server 100 through a web in a server / client environment (S1); Verifying whether the received user requirement and the constraint conflict (S2); Calculating a solution of a housing space based on the verified data (S5); Outputting the obtained solution of the housing space problem in a two-dimensional design drawing (S6); In the space planning method through the web (WEB) having a step (S9 to S10) for generating the VRML code for the output two-dimensional design drawings and output to the three-dimensional design drawings, If an error occurs due to a collision of constraints in the step S2 of verifying whether the received user requirements and the constraints are conflicted, show a correction message to the user and request re-entry (S3, S4). Equipped; In the step of solving the housing space problem (S5), a resource allocation method based on the Constraint Satisfaction Problems (CSP) solution is used as a method for allocating a room in the housing space, but the user satisfaction is improved. The method of planning a housing space in a web environment, comprising the steps (S7, S8) of solving a housing space problem using a trial-and-error method. (delete) (delete)